Abstract
Pseudorandom switching lemmas---randomness-efficient algorithms for sampling restrictions that dramatically simplify depth-two circuits---were first studied by Ajtai and Wigderson in their pioneering 1985 work on unconditional derandomization. While numerous pseudorandom switching lemmas have since been developed and employed in a variety of contexts, one that achieves the optimal parameters of Hastad's influential 1986 switching lemma (which uses full randomness) was only obtained recently by Trevisan and Xue in 2013.
In this work we derandomize recently-developed ``multi-switching" lemmas, powerful generalizations of Hastad's 1986 switching lemma that deal with families of depth-two circuits. Our pseudorandom multi-switching lemma---a randomness-efficient algorithm for sampling restrictions that simultaneously simplify all circuits in a family---achieves the optimal parameters obtained by Impagliazzo, Matthews, and Paturi (2012) and Hastad (2014) using full randomness.
We employ our pseudorandom multi-switching lemma to give the best known pseudorandom generators for two well-studied classes in unconditional derandomization: we give an $\eps$-PRG for the class of size-$M$ depth-$d$ AC^0 circuits with seed length $\log(M)^{d+O(1)}\cdot \log(1/\eps)$, and an $\eps$-PRG for the class of $S$-sparse $\F_2$ polynomials with seed length $2^{O(\sqrt{\log S})}\cdot \log(1/\eps)$.
Our results bring the state of the art for unconditional derandomization of these classes into sharp alignment with the state of the art for computational hardness: improving on the seed lengths of either PRG would require breakthrough progress on longstanding and notorious circuit lower bounds.
Joint work with Li-Yang Tan.