Log-Seed Pseudorandom Generators via Iterated Restrictions

摘要

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The ``iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length polylo g n or even O ( 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 read-once depth- 2 AC 0 [ ] formulas with seed length O ( log n ) + O ( log (1 )) . In particular, our PRG achieves optimal seed length O ( log n ) with near-optimal error = exp ( ? ( log n )) . Even for constant error, the best prior PRG for this model (which includes read-once CNFs and read-once F 2 -polynomials) has seed length ( log n ( log log n ) 2 ) [Lee19]. A key step in the analysis of our PRG is a tail bound for subset-wise symmetric polynomials, a generalization of elementary symmetric polynomials. Like elementary symmetric polynomials, subset-wise symmetric polynomials provide a way to organize the expansion of m i =1 (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. Subset-wise 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 [GY14] on elementary symmetric polynomials.