ECCC-Report TR16-143https://eccc.weizmann.ac.il/report/2016/143Comments and Revisions published for TR16-143en-usThu, 15 Sep 2016 11:10:17 +0300
Paper TR16-143
| An Almost Cubic Lower Bound for $\Sigma\Pi\Sigma$ Circuits Computing a Polynomial in VP |
Nikhil Balaji,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2016/143In this note, we prove that there is an explicit polynomial in VP such that any $\Sigma\Pi\Sigma$ arithmetic circuit computing it must have size at least $n^{3-o(1)}$. Up to $n^{o(1)}$ factors, this strengthens a recent result of Kayal, Saha and Tavenas (ICALP 2016) which gives a polynomial in VNP with the property that any $\Sigma\Pi\Sigma$ arithmetic circuit computing it must have size $\tilde{\Omega}(n^{3})$.
Thu, 15 Sep 2016 11:10:17 +0300https://eccc.weizmann.ac.il/report/2016/143