Abstract
There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The "iterated restrictions" approach, pioneered by Ajtai and Wigderson [Ajtai and Wigderson, 1989], has provided PRGs with seed length polylog n or even Õ(log n) for several restricted models of computation. Can this approach ever achieve the optimal seed length of O(log n)?
In this work, we answer this question in the affirmative. Using the iterated restrictions approach, we construct an explicit PRG for readonce depth2 AC⁰[⊕] formulas with seed length O(log n) + Õ(log(1/ε)). In particular, we achieve optimal seed length O(log n) with nearoptimal error ε = exp(Ω̃(log n)). Even for constant error, the best prior PRG for this model (which includes readonce CNFs and readonce ?₂polynomials) has seed length Θ(log n ⋅ (log log n)²) [Chin Ho Lee, 2019].
A key step in the analysis of our PRG is a tail bound for subsetwise symmetric polynomials, a generalization of elementary symmetric polynomials. Like elementary symmetric polynomials, subsetwise symmetric polynomials provide a way to organize the expansion of ∏_{i=1}^m (1 + y_i). Elementary symmetric polynomials simply organize the terms by degree, i.e., they keep track of the number of variables participating in each monomial. Subsetwise symmetric polynomials keep track of more data: for a fixed partition of [m], they keep track of the number of variables from each subset participating in each monomial. Our tail bound extends prior work by Gopalan and Yehudayoff [Gopalan and Yehudayoff, 2014] on elementary symmetric polynomials.
BibTeX  Entry
@InProceedings{doron_et_al:LIPIcs:2020:12558,
author = {Dean Doron and Pooya Hatami and William M. Hoza},
title = {{LogSeed Pseudorandom Generators via Iterated Restrictions}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {6:16:36},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12558},
URN = {urn:nbn:de:0030drops125586},
doi = {10.4230/LIPIcs.CCC.2020.6},
annote = {Keywords: Pseudorandom generators, Pseudorandom restrictions, Readonce depth2 formulas, Parity gates}
}
Keywords: 

Pseudorandom generators, Pseudorandom restrictions, Readonce depth2 formulas, Parity gates 
Collection: 

35th Computational Complexity Conference (CCC 2020) 
Issue Date: 

2020 
Date of publication: 

17.07.2020 