TR16-137 Authors: Mrinal Kumar, Ramprasad Saptharishi

Publication: 3rd September 2016 14:45

Downloads: 1430

Keywords:

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.