@article{doi:10.1137/140957123,
    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 arithmetic branching program of size \$s\$), then it can also be computed by a depth-3 circuit (i.e., a \$\Sigma \Pi \Sigma\$ circuit) of size \$\exp(O(\sqrt{d \log n \log d\log s}))\$ (respectively, of size \$\exp(O(\sqrt{d \log n \log s}))\$. In particular this yields a \$\Sigma \Pi \Sigma\$ circuit of size \$\exp(O(\sqrt{d} \cdot \log d))\$ computing the \$d \times d\$ determinant \$\mathsf{Det}\\_d\$. It also means that if we can prove a lower bound of \$\exp(\omega(\sqrt{d} \cdot \log d))\$ on the size of any \$\Sigma \Pi \Sigma\$ circuit computing the \$d \times d\$ permanent \$\mathsf{Perm}\\_d\$, then we get superpolynomial lower bounds for the size of any arithmetic branching program computing \$\mathsf{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 \$\mathsf{Det}\\_d\$ or \$\mathsf{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))\$.},
    Author = {Gupta, Ankit and Kamath, Pritish and Kayal, Neeraj and Saptharishi, Ramprasad},
    EPrint = {https://doi.org/10.1137/140957123},
    File = {Arithmetic Circuits- A Chasm at Depth Three - gupta-et-al-2016-arithmetic-circuits-a-chasm-at-depth-3.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {3},
    Pages = {1064-1079},
    Title = {Arithmetic Circuits: A Chasm at Depth 3},
    URL = {https://doi.org/10.1137/140957123},
    Volume = {45},
    Year = {2016},
    bdsk-url-1 = {https://doi.org/10.1137/140957123},
    date-added = {2023-10-06 11:17:42 +0200},
    date-modified = {2023-10-06 11:17:42 +0200},
    doi = {10.1137/140957123}
}

@article{doi:10.1137/140957123, 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 arithmetic branching program of size \$s\$), then it can also be computed by a depth-3 circuit (i.e., a \$\Sigma \Pi \Sigma\$ circuit) of size \$\exp(O(\sqrt{d \log n \log d\log s}))\$ (respectively, of size \$\exp(O(\sqrt{d \log n \log s}))\$. In particular this yields a \$\Sigma \Pi \Sigma\$ circuit of size \$\exp(O(\sqrt{d} \cdot \log d))\$ computing the \$d \times d\$ determinant \$\mathsf{Det}\_d\$. It also means that if we can prove a lower bound of \$\exp(\omega(\sqrt{d} \cdot \log d))\$ on the size of any \$\Sigma \Pi \Sigma\$ circuit computing the \$d \times d\$ permanent \$\mathsf{Perm}\_d\$, then we get superpolynomial lower bounds for the size of any arithmetic branching program computing \$\mathsf{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 \$\mathsf{Det}\_d\$ or \$\mathsf{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))\$.}, Author = {Gupta, Ankit and Kamath, Pritish and Kayal, Neeraj and Saptharishi, Ramprasad}, EPrint = {https://doi.org/10.1137/140957123}, File = {Arithmetic Circuits- A Chasm at Depth Three - gupta-et-al-2016-arithmetic-circuits-a-chasm-at-depth-3.pdf}, Journal = {SIAM Journal on Computing}, Number = {3}, Pages = {1064-1079}, Title = {Arithmetic Circuits: A Chasm at Depth 3}, URL = {https://doi.org/10.1137/140957123}, Volume = {45}, Year = {2016}, bdsk-url-1 = {https://doi.org/10.1137/140957123}, date-added = {2023-10-06 11:17:42 +0200}, date-modified = {2023-10-06 11:17:42 +0200}, doi = {10.1137/140957123} }