Theory of Computing
-------------------
Title     : Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas
Authors   : Rocco A. Servedio and Li-Yang Tan
Volume    : 18
Number    : 4
Pages     : 1-46
URL       : https://theoryofcomputing.org/articles/v018a004

Abstract
--------

We give the best known pseudorandom generators for two touchstone
classes in unconditional derandomization: small-depth circuits and
sparse F_2 polynomials. Our main results are an $\eps$-PRG for the
class of size-$M$ depth-$d$ AC0 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)$.
These 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 for all parameter settings: substantially
improving on the seed lengths of either PRG would require a breakthrough
on longstanding and notorious circuit lower bound problems.

The key enabling ingredient in our approach is a new _pseudorandom
multi-switching lemma_. We derandomize recently developed _multi_-
switching lemmas, which are powerful generalizations of Hastad's
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 parameters obtained by the (full randomness)
multi-switching lemmas of Impagliazzo, Matthews, and Paturi (SODA'12)
and Hastad (SICOMP 2014). This optimality of our derandomization
translates into the optimality (given current circuit lower bounds) of
our PRGs for AC0 and sparse F_2 polynomials.

-----------------

A preliminary version of this paper appeared in the
Proceedings of the 23rd International Conference on 
Randomization and Computation (RANDOM 2019).