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.

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.