Revision #1 Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Accepted on: 5th March 2013 11:50

Downloads: 3013

Keywords:

We show that, over $\mathbb{Q}$, 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 $\Sigma \Pi \Sigma$-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 $\Sigma \Pi \Sigma$ circuit of size $\exp(\sqrt{d} \cdot \log d)$ computing the $d \times d$ determinant $\mathrm{Det}_d$. It also means that if we can prove a lower bound of $\exp(\omega(\sqrt{d} \cdot \log^{3/2} d))$ on the size of any $\Sigma \Pi \Sigma$-circuit computing the $d \times d$ permanent $\mathrm{Perm}_d$ then we get superpolynomial lower bounds for the size of any arithmetic circuit computing $\mathrm{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 $\mathrm{Det}_d$ or $\mathrm{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))$.

The depth reduction now works over any field of zero characteristic (the earlier version required algebraic closure additionally)

TR13-026 Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Publication: 11th February 2013 16:48

Downloads: 3770

Keywords:

We show that, over $\mathbb{C}$, 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 $\Sigma \Pi \Sigma$-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 $\Sigma \Pi \Sigma$ circuit of size $\exp(\sqrt{d} \cdot \log d)$ computing the $d \times d$ determinant $\mathrm{Det}_d$. It also means that if we can prove a lower bound of $\exp(\omega(\sqrt{d} \cdot \log^{3/2} d))$ on the size of any $\Sigma \Pi \Sigma$-circuit computing the $d \times d$ permanent $\mathrm{Perm}_d$ then we get superpolynomial lower bounds for the size of any arithmetic circuit computing $\mathrm{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 $\mathrm{Det}_d$ or $\mathrm{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))$.