ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR16-153 | 27th February 2017 15:13

On $\Sigma\wedge\Sigma\wedge\Sigma$ Circuits: The Role of Middle $\Sigma$ Fan-in, Homogeneity and Bottom Degree

RSS-Feed




Revision #3
Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah
Accepted on: 27th February 2017 15:13
Downloads: 46
Keywords: 


Abstract:

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.



Changes to previous version:

Some of the bounds are improved.


Revision #2 to TR16-153 | 27th February 2017 15:13

On $\Sigma\wedge\Sigma\wedge\Sigma$ Circuits: The Role of Middle $\Sigma$ Fan-in, Homogeneity and Bottom Degree





Revision #2
Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah
Accepted on: 27th February 2017 15:13
Downloads: 55
Keywords: 


Abstract:

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.



Changes to previous version:

Some of the bounds are improved.


Revision #1 to TR16-153 | 30th September 2016 12:34

Lower Bounds for Projections of Power Symmetric Polynomials





Revision #1
Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah
Accepted on: 30th September 2016 12:34
Downloads: 123
Keywords: 


Abstract:

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$.



Changes to previous version:

Title was incorrectly entered in the info. Changed it now.


Paper:

TR16-153 | 28th September 2016 06:30

Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials





TR16-153
Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah
Publication: 28th September 2016 17:25
Downloads: 192
Keywords: 


Abstract:

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$.



ISSN 1433-8092 | Imprint