Lower bounds for bounded depth arithmetic circuits
Tuesday, March 28, 2017, 02:00pm
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.
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 progress towards both these objectives. Some of our main results include a strong hierarchy theorem for bottom fan-in for homogeneous depth-4 circuits, a super-polynomial lower bound for homogeneous depth-4 circuits, a 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.
Speaker: Mrinal Kumar
Location : CoRE A (301)
Prof. Swastik Kopparty (Advisor) , Prof. Shubhangi Saraf (Advisor) , Prof. Eric Allender, Prof. Ran Raz (Princeton University)
Event Type: PhD Defense
Dept. of Computer Science