期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this note, we prove that there is an explicit polynomial in VP such that any 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 arithmetic circuit computing it must have size ( n 3 ) .
