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.