An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
复制标题
深度三算术电路的近似三次下界
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Sébastien Tavenas
中科院分区：
文献类型：
--
作者：
N. Kayal;Chandan Saha;Sébastien Tavenas
我们在任何深度的三个算术电路的大小上显示了一个几乎立方的下限，计算在任何字段上N变量中的显式多项式多项式。这改善了Shpilka和Wigderson先前已知的二次下限[CCC，1999]。
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].