License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.10
URN: urn:nbn:de:0030-drops-142843
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14284/
Chattopadhyay, Eshan ;
Gaitonde, Jason ;
Lee, Chin Ho ;
Lovett, Shachar ;
Shetty, Abhishek
Fractional Pseudorandom Generators from Any Fourier Level
Abstract
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2019] that exploit L₁ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the k-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with k. This interpolates previous works, which either require Fourier bounds on all levels [Chattopadhyay et al., 2019], or have polynomial dependence on the error parameter in the seed length [Eshan Chattopadhyay et al., 2019], and thus answers an open question in [Eshan Chattopadhyay et al., 2019]. As an example, we show that for polynomial error, Fourier bounds on the first O(log n) levels is sufficient to recover the seed length in [Chattopadhyay et al., 2019], which requires bounds on the entire tail.
We obtain our results by an alternate analysis of fractional PRGs using Taylor’s theorem and bounding the degree-k Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the L₁ notion in previous works. By generalizing a connection established in [Chattopadhyay et al., 2020], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for ?₂ polynomials with seed length close to the state-of-the-art construction due to Viola [Emanuele Viola, 2009].
BibTeX - Entry
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2021.10,
author = {Chattopadhyay, Eshan and Gaitonde, Jason and Lee, Chin Ho and Lovett, Shachar and Shetty, Abhishek},
title = {{Fractional Pseudorandom Generators from Any Fourier Level}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {10:1--10:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-193-1},
ISSN = {1868-8969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14284},
URN = {urn:nbn:de:0030-drops-142843},
doi = {10.4230/LIPIcs.CCC.2021.10},
annote = {Keywords: Derandomization, pseudorandomness, pseudorandom generators, Fourier analysis}
}
|
Keywords: |
|
Derandomization, pseudorandomness, pseudorandom generators, Fourier analysis |
|
Collection: |
|
36th Computational Complexity Conference (CCC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
08.07.2021 |
