Skip to content Skip to navigation
Pre-Defense
2/7/2017 02:00 pm
CBIM 22

Lower Bounds for Bounded Depth Arithmetic Circuits

Mrinal Kumar, Ph.D Student

Defense Committee: Prof. Swastik Kopparty(Chair), Prof. Shubhangi Saraf (Chair), Prof. Eric Allender and Prof. Ran Raz (Princeton University)

Abstract

Proving lower bounds for arithmetic circuits is a fundamental problem in theoretical computer science and mathematics. In recent years, an approach to this problem has emerged via the depth reduction results of Agrawal and Vinay, which show that strong enough lower bounds for extremely structured bounded depth circuits (even homogeneous depth-4 or depth-5 circuits) suffice for general arithmetic circuit lower bounds.   

For 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, and make some concrete progress towards both these objectives. Some of our main results include a strong hierarchy theorem for bottom fan-in for homogeneous depth-4 circuits, the first super-polynomial lower bound for homogeneous depth-4 circuits, the first super-polynomial lower bounds for homogeneous depth-5 circuits over finite fields, and some results indicating that the parameters for depth reduction to homogeneous depth-4 circuits might be close to optimal in a fairly strong sense - substantially better general depth reduction results to homogeneous depth-4 circuits might be unlikely even for linear size homogeneous depth-5 circuits.