ECCC-Report TR13-026https://eccc.weizmann.ac.il/report/2013/026Comments and Revisions published for TR13-026en-usTue, 05 Mar 2013 11:50:17 +0200
Revision 1
| Arithmetic circuits: A chasm at depth three |
Ankit Gupta,
Pritish Kamath,
Neeraj Kayal,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2013/026#revision1We 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))$.Tue, 05 Mar 2013 11:50:17 +0200https://eccc.weizmann.ac.il/report/2013/026#revision1
Paper TR13-026
| Arithmetic circuits: A chasm at depth three |
Ankit Gupta,
Pritish Kamath,
Neeraj Kayal,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2013/026We 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))$.Mon, 11 Feb 2013 16:48:58 +0200https://eccc.weizmann.ac.il/report/2013/026