Lower Bounds for Bounded Depth Arithmetic Circuit

Proving lower bounds for arithmetic circuits is a problem of fundamental importance in theoretical computer science. In recent years, an approach to this problem has emerged via the depth reduction results of Agrawal and Vinay [AV08], which show that strong enough lower bounds for extremely structured bounded depth circuits (even homogeneous depth-4 circuits) suffice for general arithmetic circuits lower bounds. In this dissertation, we study homogeneous depth-4 and homogeneous depth-5 arithmetic circuits with a view towards proving strong lower bounds, and understanding the optimality of the depth reduction results. Some of our main results are as follows.;• We show a hierarchy theorem for bottom fan-in for homogeneous depth-4 circuits with bounded bottom fan-in. More formally, we show that there for a wide range of choice of parameter t, there is a homogeneous polynomial in n variables of degree d = ntheta(1) which can be computed by a homogeneous depth-4 circuit of bottom fan-in t, but any homogeneous depth-4 circuit of bottom fan-in at most t=20 must have top fan-in n O(d/t).;• We show that there is an explicit polynomial family such that any homogeneous depth-4 arithmetic circuit computing it must have super-polynomial size. These were the first superpolynomial lower bounds for homogeneous depth-4 circuits with no restriction on top or bottom fan-in. Simultaneously and independently, a similar lower bound was also proved by Kayal et al [KLSS14b].;• We show that any homogeneous depth-4 circuit computing the iterated matrix multiplication polynomial in n variables and degree d = ntheta(1) must have size at least nO(√d). This shows that the upper bounds of depth reduction from general arithmetic circuits to homogeneous depth-4 circuits are almost optimal, up to a constant in the exponent. Moreover, these were the first nO(√d) lower bounds for homogeneous depth-4 circuits over all fields. Prior to our work, Kayal et al. [KLSS14a] had shown such a lower bound over the fields of characteristic zero.;• We show that there is a family of polynomials in n variables and degree d = O(log2 n) which can be computed by linear size homogeneous depth-5 circuits and polynomial size non-homogeneous depth-3 circuits but require homogeneous depth-4 circuits of size nO(√d). In addition to indicating the power of increased depth, and non-homogeneity, these results also show that for the range of parameters considered here, the upper bounds for the depth reduction results [AV08, Koi12, Tav15] are close to optimal in a very strong sense : a general depth reduction to homogeneous depth-4 circuits of size no(√d) is not possible even for homogeneous depth-5 circuits of linear size.;• We show an exponential lower bound for homogeneous depth-5 circuits computing an explicit polynomial over all finite fields of constant size. For any non-binary field, these were the first such super-polynomial lower bounds, and prior to our work, even cubic lower bounds were not known for homogeneous depth-5 circuits.;On the way to our proofs, we study the complexity of some natural polynomial families (for instance, homogeneous depth-4, depth-5 circuits, iterated matrix multiplication) with respect to many existing partial derivative based complexity measures, and also define and analyze some new variants of these measures [KS14, KS15b].