Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### An almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Revision #2
Authors: Neeraj Kayal, Chandan Saha, Sébastien Tavenas
Accepted on: 1st April 2016 11:21
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
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
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.