Friday, July 17, 2015 - 1:15pm to 4:15pm

Refreshments:

Pizza at 1:00pm

Location:

Barton room on the 1st floor of One Memorial Drive building

Speaker:

Mrinal Kumar

Biography:

Rutgers

Seminar group:

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.

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.