Amir Shpilka: Depth Reduction for Algorithmic Circuits

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.