Can arithmetic computation be efficiently parallelized? Specifically, if a multivariate polynomial f is computed by an arithmetic circuit of size s, what is the size of the smallest circuit of depth d computing f? Building on the seminal work of Valiant, Skyum, Berkowitz and Rackoff in 1983, recent results on depth reduction have shown that nontrivial depth reduction is possible even for target depth being d=3 and d=4. The resulting circuit has size roughly s^sqrt(deg(f)). Is this optimal?

The results on depth reduction also yield a potential route to prove lower bounds for arithmetic circuits - via proving strong enough lower bounds for low depth circuits. We will also see recent lower bounds for such low depth circuits which yield optimality of depth reduction in some of these settings (and come tantalizingly close to the threshold required to prove superpolynomial lower bounds for general circuits).