An Improved Lower Bound for Depth four Arithmetic Circuits
MetadataShow full item record
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).
Showing items related by title, author, creator and subject.
Low Power And Low Spur Frequency Synthesizer Circuit Techniques For Energy Efficient Wireless Transmitters Manikandan, R R (2017-09-07)There has been a huge rise in interest in the design of energy efficient wireless sensor networks (WSN) and body area networks (BAN) with the advent of many new applications over the last few decades. The number of sensor ...
Time-based All-Digital Technique for Analog Built-in Self Test Vasudevamurthy, Rajath (2017-11-30)A scheme for Built-in-Self-Test (BIST) of analog signals with minimal area overhead, for measuring on-chip voltages in an all-digital manner is presented in this thesis. With technology scaling, the inverter switching times ...
Process Variability-Aware Performance Modeling In 65 nm CMOS Harish, B P (2011-02-25)With the continued and successful scaling of CMOS, process, voltage, and temperature (PVT), variations are increasing with each technology generation. The process variability impacts all design goals like performance, ...