__
TR16-143 | 15th September 2016 09:12
__

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

**Abstract:**
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})$.