Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-006 | 1st April 2016 11:21

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits

RSS-Feed




Revision #2
Authors: Neeraj Kayal, Chandan Saha, Sébastien Tavenas
Accepted on: 1st April 2016 11:21
Downloads: 360
Keywords: 


Abstract:

We show an $\Omega \left(\frac{n^3}{(\ln n)^3}\right)$ lower bound on
the number of gates of any depth three ($\Sigma \Pi \Sigma$) 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 (1999, 2001).



Changes to previous version:

In the previous version, the lower bound was for the number of edges which we now strengthen to a lower bound on the number of gates in the depth three circuit.


Revision #1 to TR16-006 | 22nd January 2016 19:51

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits





Revision #1
Authors: Neeraj Kayal, Chandan Saha, Sébastien Tavenas
Accepted on: 22nd January 2016 19:51
Downloads: 717
Keywords: 


Abstract:

We show an $\Omega \left(\frac{n^3}{(\ln n)^2}\right)$ lower bound on the size of any depth three ($\sum\prod\sum$) 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.



Changes to previous version:

We just fixed a small problem with a TeX command in the abstract.


Paper:

TR16-006 | 22nd January 2016 19:28

An almost Cubic Lower Bound for Depth Three Arithmetic Circuits





TR16-006
Authors: Neeraj Kayal, Chandan Saha, Sébastien Tavenas
Publication: 22nd January 2016 19:37
Downloads: 390
Keywords: 


Abstract:

We show an $\Omega \left(\frac{n^3}{(\ln n)^2}\right)$ lower bound on the size of any depth three ($\SPS$) 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.



ISSN 1433-8092 | Imprint