We study polynomials computed by depth five $\Sigma\wedge\Sigma\wedge\Sigma$ circuits, i.e., polynomials of the form $\sum_{i=1}^t Q_i$ where $Q_i = \sum_{j=1}^{r_i}\ell_{ij}^{d_{ij}}$, $\ell_{ij}$ are linear forms and $r_i$, $t\ge 0$. These circuits are a natural generalization of the well known class of $\Sigma\wedge\Sigma$ circuits and received significant attention recently. We prove exponential lower bound for the monomial $x_1\cdots x_n$ against the following sub-classes of $\Sigma\wedge\Sigma\wedge\Sigma$ circuits:
\begin{itemize}
\item Depth four homogeneous $\Sigma\wedge\Sigma \wedge$ arithmetic circuits.
\item Depth five $\Sigma\wedge\Sigma^{[\le n]}\wedge^{[\ge 21]}\Sigma$ and $\Sigma\wedge\Sigma^{[\le 2^{\sqrt{n}/1000}]}\wedge^{[\ge \sqrt{n}]}\Sigma$ arithmetic circuits where the bottom $\Sigma$ gate is homogeneous;
\end{itemize}
Our results show precisely how the fan-in of the middle $\Sigma$ gates, the degree of the bottom powering gates and the homogeneity at the bottom $\Sigma$ gates play a crucial role in the computational power of $\Sigma\wedge\Sigma\wedge\Sigma$ circuits.
Some of the bounds are improved.
We study polynomials computed by depth five $\Sigma\wedge\Sigma\wedge\Sigma$ circuits, i.e., polynomials of the form $\sum_{i=1}^t Q_i$ where $Q_i = \sum_{j=1}^{r_i}\ell_{ij}^{d_{ij}}$, $\ell_{ij}$ are linear forms and $r_i$, $t\ge 0$. These circuits are a natural generalization of the well known class of $\Sigma\wedge\Sigma$ circuits and received significant attention recently. We prove exponential lower bound for the monomial $x_1\cdots x_n$ against the following sub-classes of $\Sigma\wedge\Sigma\wedge\Sigma$ circuits:
\begin{itemize}
\item Depth four homogeneous $\Sigma\wedge\Sigma \wedge$ arithmetic circuits.
\item Depth five $\Sigma\wedge\Sigma^{[\le n]}\wedge^{[\ge 21]}\Sigma$ and $\Sigma\wedge\Sigma^{[\le 2^{\sqrt{n}/1000}]}\wedge^{[\ge \sqrt{n}]}\Sigma$ arithmetic circuits where the bottom $\Sigma$ gate is homogeneous;
\end{itemize}
Our results show precisely how the fan-in of the middle $\Sigma$ gates, the degree of the bottom powering gates and the homogeneity at the bottom $\Sigma$ gates play a crucial role in the computational power of $\Sigma\wedge\Sigma\wedge\Sigma$ circuits.
Some of the bounds are improved.
The power symmetric polynomial on $n$ variables of degree $d$ is defined as
$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers
of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by
depth five circuits with summation and powering gates (i.e., $ \sum\bigwedge\sum\bigwedge\sum$ circuits). We show
$2^{\Omega(n)}$ size lower bounds for $x_1\cdots x_n$ against the following models:
\begin{itemize}
\item Depth five $\sum\bigwedge\sum^{\le n}\bigwedge^{\ge 21}\sum$ arithmetic circuits where the bottom $\sum$ gate is homogeneous;
\item Depth four $\sum\bigwedge\sum^{\le n}\bigwedge$ arithmetic circuits.
\end{itemize}
Together with the ideas in [Forbes, FOCS 2015] our lower bounds imply deterministic $n^{\poly(\log n)}$ black-box
identity testing algorithms for the above classes of arithmetic circuits.
Our technique uses a measure that involves projecting the partial derivative space of the given polynomial to
its multilinear subspace and then setting a subset of variables to $0$.
Title was incorrectly entered in the info. Changed it now.
The power symmetric polynomial on $n$ variables of degree $d$ is defined as
$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers
of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by
depth five circuits with summation and powering gates (i.e., $ \sum\bigwedge\sum\bigwedge\sum$ circuits). We show
$2^{\Omega(n)}$ size lower bounds for $x_1\cdots x_n$ against the following models:
\begin{itemize}
\item Depth five $\sum\bigwedge\sum^{\le n}\bigwedge^{\ge 21}\sum$ arithmetic circuits where the bottom $\sum$ gate is homogeneous;
\item Depth four $\sum\bigwedge\sum^{\le n}\bigwedge$ arithmetic circuits.
\end{itemize}
Together with the ideas in [Forbes, FOCS 2015] our lower bounds imply deterministic $n^{\poly(\log n)}$ black-box
identity testing algorithms for the above classes of arithmetic circuits.
Our technique uses a measure that involves projecting the partial derivative space of the given polynomial to
its multilinear subspace and then setting a subset of variables to $0$.