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) :

$K\geq \epsilon \frac{n}{s^{d-1}}$ for $s\geq n^{1/d}$
$K\geq \epsilon (\frac{n}{s})^{1/(d-1)}$ for $s\leq n^{1/d}$

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