ECCC-Report TR16-153https://eccc.weizmann.ac.il/report/2016/153Comments and Revisions published for TR16-153en-usMon, 27 Feb 2017 15:13:27 +0200
Revision 3
| On $\Sigma\wedge\Sigma\wedge\Sigma$ Circuits: The Role of Middle $\Sigma$ Fan-in, Homogeneity and Bottom Degree |
Christian Engels,
Raghavendra Rao B V,
Karteek Sreenivasaiah
https://eccc.weizmann.ac.il/report/2016/153#revision3We 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. Mon, 27 Feb 2017 15:13:27 +0200https://eccc.weizmann.ac.il/report/2016/153#revision3
Revision 2
| On $\Sigma\wedge\Sigma\wedge\Sigma$ Circuits: The Role of Middle $\Sigma$ Fan-in, Homogeneity and Bottom Degree |
Christian Engels,
Raghavendra Rao B V,
Karteek Sreenivasaiah
https://eccc.weizmann.ac.il/report/2016/153#revision2We 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. Mon, 27 Feb 2017 15:13:22 +0200https://eccc.weizmann.ac.il/report/2016/153#revision2
Revision 1
| Lower Bounds for Projections of Power Symmetric Polynomials |
Christian Engels,
Raghavendra Rao B V,
Karteek Sreenivasaiah
https://eccc.weizmann.ac.il/report/2016/153#revision1 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$.Fri, 30 Sep 2016 12:34:41 +0300https://eccc.weizmann.ac.il/report/2016/153#revision1
Paper TR16-153
| Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials |
Christian Engels,
Raghavendra Rao B V,
Karteek Sreenivasaiah
https://eccc.weizmann.ac.il/report/2016/153 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$.Wed, 28 Sep 2016 17:25:43 +0300https://eccc.weizmann.ac.il/report/2016/153