An Improved Lower Bound for Depth four Arithmetic Circuits

Abstract

We study the problem of proving lower bounds for depth four arithmetic circuits. Depth four circuits have been receiving much attraction when it comes to recent circuit lower bound results, as a result of the series of results culminating in the fact that strong enough lower bounds for depth four circuits will imply super-polynomial lower bounds for general arithmetic circuits, and hence solve one of the most central open problems in algebraic complexity i.e a separation between the VP and VNP classes. However despite several efforts, even for general arithmetic circuits, the best known lower bound is Omega(N log N) by Baur and Strassen (1983), where N is the number of input variables. In the case of arithmetic formulas, Kalorkoti (1985) proved a lower bound that is quadratic in the number of input variables, which has not seen any improvement since then. The situation for depth three arithmetic circuits was also similar for many years, until a recent result by Kayal et. al. (2016) achieved an almost cubic lower bound that improved over the previous best quadratic bound by Shpilka and Wigderson (1999). As the main contribution of this thesis, we prove an Omega(N^1.5) lower bound on the size of a depth four circuit, for an explicit multilinear N-variate polynomial in VNP with degree d = Theta(sqrt(N)). Our approach offers a potential route to proving a super-quadratic lower bound for depth four circuits. Taking cue from the numerous successful results recently, we use the technique of the shifted partial derivatives measure to achieve the said lower bound. Particularly, we use the Dimension of Projected Shifted Partials (DPSP) measure which has been previously used in recent depth four results. Coming to the choice of the hard polynomial, we again follow the status quo and use a variant of the Nisan-Wigderson (NW) polynomial family that has proved to be very helpful over the past few years in arithmetic circuit complexity. Finally, we do a careful analysis of Shoup-Smolensky (1997) and Raz (2010) and compare their techniques to ours. We conclude that our result can potentially be used as a starting point, and techniques similar to Kayal et. al. (2016) can likely be used to strengthen our lower bound to Omega(N^2.5), for general depth four arithmetic circuits. However, unlike depth three circuits, proving a super-quadratic lower bound for depth four circuits remains a prevalent open problem for many years. Previous work like Shoup-Smolensky and Raz implied super-linear lower bounds. To the best of our knowledge, the previous best known lower bound for general depth four circuits is Omega(N^1.33).