Arithmetic Circuits: Depth reductions, chasms and escalators

Arithmetic circuits provide a robust model to study the complexities of polynomials. Perhaps the most important question in this field is to prove strong lower bounds for explicit polynomials, like the Permanent. However, progress on proving lower bounds for even very shallow circuits seemed to stop around just depth-3 circuits. In this talk, we shall see how even depth-3 circuits in the arithmetic world can be surprisingly powerful, and how proving strong enough lower bounds for depth-3 circuits would suffice for general arithmetic circuit lower bounds.

This is joint work with Ankit Gupta, Pritish Kamath and Neeraj Kayal.

https://plus.google.com/109603448835568460155/posts