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}$

$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