Amir Shpilka: Depth Reduction for Algorithmic Circuits

Friday, April 18, 2014 - 12:45pm to 3:45pm
Pizza at 12:30pm
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Amir Shpilka

The goal of this talk is to present several depth-reduction results for arithmetic circuits. We will start by proving the seminal result of Valiant, Skyum, Berkowitz and Rackoff that VP=VNC^2, namely, that arithmetic circuits can be parallelized. We will then go over the more recent reductions to depth 4 and depth 3 circuits by Agrawal and Vinay and by Gupta, Kamath, Kayal and Saptharishi, respectively.

Time permitting we shall also discuss some of the recent lower bounds proved for depth-4 circuits.