Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-026 | 5th March 2013 11:50

Arithmetic circuits: A chasm at depth three

RSS-Feed

Abstract:

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))$.



Changes to previous version:

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


Paper:

TR13-026 | 11th February 2013 16:24

Arithmetic circuits: A chasm at depth three





TR13-026
Authors: Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Publication: 11th February 2013 16:48
Downloads: 6450
Keywords: 


Abstract:

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))$.



ISSN 1433-8092 | Imprint