Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 18 (2022) Article 4 pp. 1-46
APPROX-RANDOM 2019 Special Issue
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas
Received: June 30, 2019
Revised: December 30, 2020
Published: March 2, 2022
Download article from ToC site:
[PDF (474K)] [PS (2871K)] [Source ZIP]
Keywords: pseudorandom generators, switching lemmas, circuit complexity
ACM Classification: F.1.2
AMS Classification: 68Q17

Abstract: [Plain Text Version]

\newcommand{\acz}{\mathsf{AC^0}} \newcommand{\eps}{\epsilon} \newcommand{\F}{\mathbb{F}}

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 \acz 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 Håstad'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 Håstad (SICOMP 2014). This optimality of our derandomization translates into the optimality (given current circuit lower bounds) of our PRGs for \acz 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).