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$.
• $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)$
$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)$