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.
