Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-143 | 15th September 2016 09:12

#### An Almost Cubic Lower Bound for $\Sigma\Pi\Sigma$ Circuits Computing a Polynomial in VP

TR16-143
Authors: Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan
Publication: 15th September 2016 11:10
In 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})$.