11:45 a.m. - 12:45 p.m. & 2:00 p.m. - 3:00 p.m. Arithmetic circuits: A chasm at depth-3 (Two Talks) Ramprasad Saptarishi Chennai Mathematical Institute. 25-02-13 Abstract
Agrawal-Vinay (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 depth-4 formula of size n^{O(sqrt{d}),
thereby showing that proving good enough lowerbounds for depth-4
formulas would translate to lower bounds for formulas of arbitrary
depth. Here we show that, over complex numbers, the depth-reduction
can in fact be pushed further to depth-3 circuits. This is also the
first depth-reduction that we know which depends on the underlying
field, and is non-homogeneous (both of which are necessary hurdles to
overcome).
|