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


Mrinal Kumar


Rutgers University
Department of Computer Science
Hill Center, Room 418
New Brunswick, NJ
United States of America


Tuesday, 23 August 2016, 16:00 to 17:00


  • A-201 (STCS Seminar Room)


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).