11:45 am, Seminar Hall Lower bounds for shallow circuits Ramprasad Saptharishi TAU, Israel. 301015 Abstract Over the last 34 years, there has been a sudden surge of results in arithmetic circuit lower bounds, specifically for shallow circuits (depth 3 or 4). The main motivation for studying depth4 circuits is a result of Agrawal and Vinay (and subsequent strengthening by Koiran and Tavenas) that states that any arithmetic circuit of size s that computes an nvariate degree d polynomial can be simulated by a structured homogeneous depth4 circuit of size n^{Omega (sqrt{d})}. Flipping this around, this implies that if we can find an explicit polynomial that requires such structured depth4 circuits of size n^{omega(sqrt {d})}, then we would have proved lower bounds for general arithmetic circuits! In 2013, Gupta, Kamath, Kayal and Saptharishi showed a lower bound of 2^{Omega (sqrt{d})} for the dxd permanent or determinant using a technique called 'shifted partial derivatives' (introduced by [Kayal]). Subsequent to this result, there has been a flurry of activity with improvements of various sorts (improving the lower bound, or dealing with a larger circuit class etc.) and the current state of the art is an n^{Omega(sqrt{d})} lower bound for the class of homogeneous depth4 circuits with no structural restrictions [KayalLimayeSahaSrinivasan, KumarSaraf]. In this talk, I shall give a brief overview of the progress made in the last 3 years and put the various results in context. Then, I shall present a recent work with Mrinal Kumar that gives an exponential lower bound for depth5 circuits over small finite fields that combines the techniques developed so far with an old result of GrigorievKarpinski for depth3 lower bounds.
