An improved derandomization of the switching lemma

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 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 provablypseudorandom with respect to AC 0 -circuits (e.g., [AW85, TX13, GW14, SS16, AS17, ST17, ST19, BDSG + 18, DHH19, Tel19]).

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 ε-fools size-m, depth-D circuits with n-bit inputs using only O(log(m/ε) D • log n) random bits. In particular, we obtain (modulo the log log-factors hidden in the O-notation) a dependence on m/ε which is best-possible with respect to currently-known AC 0 -circuit lower bounds.