文章基本信息

标题：An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits
本地全文：下载
作者：Neeraj Kayal ; Chandan Saha ; S{\'e}bastien Tavenas 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：33:1-33:15
DOI：10.4230/LIPIcs.ICALP.2016.33
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We show an almost cubic lower bound on the size of any depth three arithmetic circuit computing an explicit multilinear polynomial in n variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson [CCC, 1999].
关键词：arithmetic circuits; depth-3 circuits; shifted partials