Chennai Mathematical Institute


11.00 am, Seminar Hall
On some lower bounds in Arithmetic Circuit complexity

Suryajith Chillara
Chennai Mathematical Institute.


An arithmetic circuit is a most natural and a standard model of computation for polynomials. To separate algebraic-P (VP) from algebraic-NP (VNP), we need to show that an explicit polynomial can not be computed by a polynomial sized arithmetic circuits.

Recently, it was shown by Agrawal and Vinay [FOCS 2008] that it is "sufficient" to prove "strong" circuit size lower bounds against depth 4 circuits and this would imply super polynomial circuit size lower bounds. Gupta, Kamath, Kayal and Saptharishi [FOCS 2013] extended this connection to depth three circuits, over fields of characteristic zero.

In this thesis we present two combinatorial frameworks that help prove lower bounds for 1. bounded fan-in depth four circuits, and 2. general depth three circuits over fixed-size finite fields. The framework at depth four gives an unified approach to cleanly prove the best known results for two explicit polynomials, and using the one at depth three, we prove the best known lower bounds for the same explicit polynomials over fixed-size finite fields. We further investigate their determinantal complexity and show some tight bounds for one of those.

We also extend the work of Raz [J.ACM 2013] and establish a connection between tensor rank and homogeneous formula size lower bounds under a certain range of parameters.

(Based on joint works with Mrinal Kumar, Partha Mukhopadhyay, Ramprasad Saptharishi and V Vinay.)