Arithmetic Circuits: A chasm at depth three

Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi

October 2013

We show that, over Q (the field of rational numbers), if an n-variate polynomial of degree d=n^{O}(1) is computable by an arithmetic circuit of size s (respectively by an algebraic branching program of size s) then it can also be computed by a depth three circuit (i.e. a Sum-Product-Sum circuit) of size exp(sqrt(d*log d*log n*log s)) (respectively of size exp(sqrt(d*log n*log s)) ). In particular this yields a circuit of size exp(sqrt(d*logd)) computing the d-by-d determinant Det_{d}. It also means that if we can prove a lower bound of exp(omega(√(d log^{2} d))) on the size of any depth three circuit computing the d-by-d permanent Perm_{d} then we get superpolynomial lower bounds for the size of any arithmetic circuit computing Perm_{d}. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds.

The circuits that we construct have the property that (some of) the intermediate polynomials have degree much higher than d. Indeed such a counterintuitive construction is unavoidable - it is known that in any circuit C computing either Det_{d} or Perm_{d}, if every multiplication gate has fanin at most d (or any constant multiple thereof) then C must have size at least exp(Omega(d)).

Publication type | Inproceedings |

Published in | Foundations of Computer Science (FOCS) |

URL | http://eccc.hpi-web.de/report/2013/026/ |

Publisher | IEEE IEEE |

Awards | Invited to Special Issue of SICOMP journal |

- An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
- Efficient Reconstruction of Random Multilinear Formulas
- The complexity of the annihilating polynomial

> Publications > Arithmetic Circuits: A chasm at depth three