We prove a new derandomization of Håstad's switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size m using only \widetilde{O}(\log m) random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing objects which are in some way provably-pseudorandom with respect to AC^0-circuits.

Here, we use our new derandomization to give an improved analysis of the pseudorandom generator of Trevisan and Xue for AC^0-circuits (CCC'13): we show that the generator \varepsilon-fools size-m, depth-D circuits with n-bit inputs using only \widetilde{O}(\log(m/\varepsilon)^{D} \cdot \log n) random bits. In particular, we obtain (modulo the \log \log-factors hidden in the \widetilde{O}-notation) a dependence on m/\varepsilon which is best-possible with respect to currently-known AC^0-circuit lower bounds.

Fixed some typos.

We prove a new derandomization of Håstad's switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size m using only \widetilde{O}(\log m) random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing objects which are in some way provably-pseudorandom with respect to AC^0-circuits.

Here, we use our new derandomization to give an improved analysis of the pseudorandom generator of Trevisan and Xue for AC^0-circuits (CCC'13): we show that the generator \varepsilon-fools size-m, depth-D circuits with n-bit inputs using only \widetilde{O}(\log(m/\varepsilon)^{D} \cdot \log n) random bits. In particular, we obtain (modulo the \log \log-factors hidden in the \widetilde{O}-notation) a dependence on m/\varepsilon which is best-possible with respect to currently-known AC^0-circuit lower bounds.