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).
A corollary of the depth-reduction is a depth-3 circuit for the n x n Determinant of size exp( sqrt{n} log n ) over the complex numbers. Prior to this, nothing asymptotically better than writing it as a sum of n! monomials was known.
This talk shall present the reduction and I shall try to make it as self-contained as possible. This would also go through previous depth-reductions etc, which should provide enough motivation for the result as well.