Mrinal Kumar: Recent progress on arithmetic circuit lower bounds and exponential lower bounds for depth five circuits over finite fields

Friday, July 17, 2015 - 1:15pm to 4:15pm
Pizza at 1:00pm
Barton room on the 1st floor of One Memorial Drive building
Mrinal Kumar
Starting with a beautiful result of Gupta et al in 2012, the last few years have seen exciting progress on the problem of proving lower bounds for interesting special classes of homogeneous depth four arithmetic circuits. These lower bounds are particularly interesting since they seem to come close to resolving the algebraic analog of the P vs NP conjecture.

I will briefly talk about these developments and end with a discussion of a recent exponential lower bound for general homogeneous depth 5 arithmetic circuits over small finite fields. These are the first superpolynomial lower bounds for this model over any field other than F_2.

The talk will be based on a joint work with Ramprasad Saptharishi, and would be mostly accessible to a general theory audience.