Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-137 | 3rd September 2016 14:37

Finer separations between shallow arithmetic circuits


Authors: Mrinal Kumar, Ramprasad Saptharishi
Publication: 3rd September 2016 14:45
Downloads: 598


In this paper, we show that there is a family of polynomials $\{P_n\}$, where $P_n$ is a polynomial in $n$ variables of degree at most $d = O(\log^2 n)$, such that

1. $P_n$ can be computed by linear sized homogeneous depth-$5$ circuits.

2. $P_n$ can be computed by $poly(n)$ sized non-homogeneous depth-$3$ circuits.

3. Any homogeneous depth-$4$ circuit computing $P_n$ must have size at least $n^{\Omega(\sqrt{d})}$.

This shows that the parameters for the depth reduction results of Agrawal and Vinay[av08, koiran, Tav13] are tight for extremely restricted classes of arithmetic circuits, for instance homogeneous depth-$5$ circuits and non-homogeneous depth-$3$ circuits, and over an appropriate range of parameters, qualitatively improve a result of Kumar and Saraf [KS14], which showed that the parameters of depth reductions are optimal for algebraic branching programs.

ISSN 1433-8092 | Imprint