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* P_n can be computed by linear sized homogeneous depth-5 arithmetic circuits,* P_n can be computed by poly(n) sized non-homogeneous depth-3 arithmetic circuits.* Any homogeneous depth-4 arithmetic 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-Vinay 08, Koiran 12, Tavenas 13] 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-Saraf 14], which showed that the parameters of depth reductions are optimal for algebraic branching programs.As an added advantage, our proofs are much shorter and simpler than the two known proofs of n^{Omega(sqrt(d))} lower bound for homogeneous depth-4 circuits [Kayal-Limaye-Saha-Srinivasan 14, Kumar-Saraf 14], albeit our proofs only work when d = O(log^2(n)).
展开▼
