Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DEPTH-3 CIRCUITS:
Reports tagged with depth-3 circuits:
TR06-049 | 9th April 2006
Guy Wolfovitz

#### The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by ... more >>>

TR16-006 | 22nd January 2016
Neeraj Kayal, Chandan Saha, Sébastien Tavenas

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

Revisions: 2

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.

more >>>

ISSN 1433-8092 | Imprint