A Near Optimal Separation Between Homogeneous Depth-5 and Homogeneous Depth-4 Arithmetic Circuits

We will show that there is a family of n- variate polynomials of degree d = O(log^2 n), which can be computed by linear sized homogeneous depth-5 arithmetic circuits, where as any homogeneous depth-4 circuit computing it must have size at least n^{Omega(sqrt d)}.

This shows that for this range of parameters, the upper bounds for depth reductions to homogeneous depth-4 circuits obtained by Agrawal-Vinay, Koiran and Tavenas are tight up to constants in the exponent; even for very simple circuits like homogeneous depth-5 arithmetic circuits. Prior to this work, it was known that the depth reduction results are tight up to constants in the exponent, for algebraic branching programs (based on a joint work with Ramprasad Saptharishi).