文章基本信息

标题：An Almost Cubic Lower Bound for \Sigma\Pi\Sigma Circuits Computing a Polynomial in VP
本地全文：下载
作者：Nikhil Balaji ; Nutan Limaye ; Srikanth Srinivasan 等
期刊名称：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 ) .
关键词：arithmetic circuits ; depth-3 ; inner product ; Shifted partial derivatives