Tata Institute of Fundamental Research
A Near Optimal Separation Between Homogeneous Depth-5 and Homogeneous Depth-4 Arithmetic Circuits
STCS Colloquium
Speaker:
Mrinal Kumar (Rutgers University
Department of Computer Science
Hill Center, Room 418
New Brunswick, NJ
United States of America)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 23 Aug 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Mrinal Kumar (Rutgers University Department of Computer Science Hill Center, Room 418 New Brunswick, NJ United States of America) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 23 Aug 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).