11:45 a.m.  12:45 p.m. & 2:00 p.m.  3:00 p.m. Arithmetic circuits: A chasm at depth3 (Two Talks) Ramprasad Saptarishi Chennai Mathematical Institute. 250213 Abstract
AgrawalVinay (FOCS 2008) and Koiran (TCS 2012) showed that any degree
d polynomial computed by a polynomial sized arithmetic formula can be
equivalently computed by a depth4 formula of size n^{O(sqrt{d}),
thereby showing that proving good enough lowerbounds for depth4
formulas would translate to lower bounds for formulas of arbitrary
depth. Here we show that, over complex numbers, the depthreduction
can in fact be pushed further to depth3 circuits. This is also the
first depthreduction that we know which depends on the underlying
field, and is nonhomogeneous (both of which are necessary hurdles to
overcome).
