Computer Science/Discrete Mathematics Seminar I

Lower bounds for homogeneous depth-5 arithmetic circuits over finite fields

The last few years have seen substantial progress on the question of proving lower bounds for homogeneous depth-4 arithmetic circuits. Even though these results seem to come close to resolving the VP vs VNP question, it seems likely that the techniques involved may not be strong enough for this resolution. However, it is conceivable that we might be able to build upon these ideas to show super-polynomial lower bounds for weaker classes of arithmetic circuits, like arithmetic formula or constant depth circuits. In this talk, we will see a proof of exponential lower bounds for the class of homogeneous depth-5 circuits over small finite fields which is a modest step in this direction. The proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et al., Fournier et al. Kayal et al., K-Saraf] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski, Gregoriev-Razborov]. A key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from $\F_q^n \rightarrow \F_q$ as opposed to looking at them as a space of formal polynomials and we combine this with a tighter analysis of the lower bound of Kayal-Limaye-Saha-Srinivasan and K-Saraf for the proof. Based on joint work with Ramprasad Saptharishi.

Date & Time

March 14, 2016 | 11:15am – 12:15pm

Location

S-101

Speakers

Mrinal Kumar

Affiliation

Rutgers University