Talks
Spring 2017

# Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas

Thursday, March 9th, 2017 3:10 pm3:40 pm

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)$.