Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




TR16-143
Authors: Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan
Publication: 15th September 2016 11:10
Downloads: 1466
Keywords: 


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



ISSN 1433-8092 | Imprint