### Revision(s):

__
Revision #2 to TR16-006 | 1st April 2016 11:21
__
#### An almost Cubic Lower Bound for Depth Three Arithmetic Circuits

**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

**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

**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.