ECCC-Report TR16-137https://eccc.weizmann.ac.il/report/2016/137Comments and Revisions published for TR16-137en-usSat, 03 Sep 2016 14:45:11 +0300
Paper TR16-137
| Finer separations between shallow arithmetic circuits |
Mrinal Kumar,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2016/137In 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.
Sat, 03 Sep 2016 14:45:11 +0300https://eccc.weizmann.ac.il/report/2016/137