Revision #3 Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

Accepted on: 27th February 2017 15:13

Downloads: 811

Keywords:

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.

Revision #2 Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

Accepted on: 27th February 2017 15:13

Downloads: 636

Keywords:

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.

Revision #1 Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

Accepted on: 30th September 2016 12:34

Downloads: 471

Keywords:

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.

TR16-153 Authors: Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

Publication: 28th September 2016 17:25

Downloads: 630

Keywords:

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