Let $K=K(n,s,d)$ be the largest number such that, if a depth-$d$ circuit has size at most $2^s$, then it can agree with Parity(x) on at most $1/2+2^{-K}$ fraction of input vectors.

Theorem 12.12 states that

$K\geq cn^{1/4d}$ if $s\leq cn^{1/4d}$ for a sufficiently small constant $c>0$.
Boppana and Hastad proved the following bounds (see Hastad's thesis) : In the case of circuits of polynomial size, Ajtai (1983) proved that for every constant depth $d$,
$K\geq n^{1-c}$ for every constant $c>0$, if $s=O(\log n)$

Impagliazzo, Matthews and Paturi have recently improved this to

$K\geq \frac{n}{\mbox{polylog}(n)}$ if $s=O(\log n)$
For general $s$ their bound is
$K\geq \frac{n}{p^{d-1}}$ where $p=O(s-\log n+d\log d)$
A similar result was recently proved also by Hastad; see ECCC report.
Return to the home page of the book