Speaker:
Affiliation:
Rutgers University
Department of Computer Science
Hill Center, Room 418
New Brunswick, NJ
United States of America
Webpage:
Time:
Venue:
- A-201 (STCS Seminar Room)
Organisers:
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).