Arithmetic Circuits: A Chasm at Depth Three

摘要

We show that, over Q, if an n-variate polynomial of degree d = nO(1) is computable by an arithmetic circuit of size s (respectively by an arithmetic branching program of size s) then it can also be computed by a depth three circuit (i.e. a Sigma Pi Sigma-circuit) of size exp(O(sqrtd log n log d log s)) (respectively of size exp(O(sqrtd log n log s)). In particular this yields a Sigma Pi Sigma circuit of size exp(O(sqrtd log d)) computing the dxd determinant Det_d. It also means that if we can prove a lower bound of exp(omega(sqrtd log d)) on the size of any Sigma Pi Sigma-circuit computing the dxd permanent Perm_d then we get super polynomial lower bounds for the size of any arithmetic branching program computing Perm_d. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds. The Sigma Pi Sigma 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 Sigma Pi Sigma 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)).