## A Derandomized Switching Lemma and an Improved Derandomization of AC0

by Luca Trevisan and TongKe Xuey.

#### Oded's comments

As can be deduced from prior postings
(cf., e.g., Nr. 87 and 93),
I'm excited about any progress regarding derandomization of AC0.
The current work reduces the seed length from a level that seems
best within the Nisan-Wigderson construction paradigm
modulo the best known lower bound techniques
to a level that seems best only modulo the latter.

#### The original abstract

We describe a new pseudorandom generator for AC0. Our generator
$\epsilon$-fools circuits of depth $d$ and size $M$ and uses a
seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous
best construction for $d \geq 3$ was due to Nisan, and had seed
length $O(\log^{2d+6} M/\epsilon)$.
A seed length of $O(\log^{2d + \Omega(1)} M)$ is best possible
given Nisan-type generators and the current state of circuit
lower bounds; Seed length $\Omega(\log^d M/\epsilon)$ is a
barrier for any pseudorandom generator construction given the
current state of circuit lower bounds. For $d=2$, a pseudorandom
generator of seed length $\tilde O(\log^2 M/\epsilon)$ was known.

Our generator is based on a ``pseudorandom restriction''
generator which outputs restrictions that satisfy the conclusions
of the Hastad Switching Lemma and that uses a seed of
polylogarithmic length.

Back to
list of Oded's choices.