Fractional pseudorandom generators from any fourier level

DOI10.4230/LIPICS.CCC.2021.10MaRDI QIDQ6115362zbMATH OpenOpenAlexFDO

Authors Eshan Chattopadhyay, Chin Ho Lee, Shachar Lovett, Abhishek Shetty

Publication date 12 July 2023

Full work available at URL https://arxiv.org/abs/2008.01316

zbMATH Keywords

derandomizationFourier analysispseudorandom generatorspseudorandomness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit $L_1$ 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 [CHHL19], or have polynomial dependence on the error parameter in the seed length [CHLT10], and thus answers an open question in [CHLT19]. As an example, we show that for polynomial error, Fourier bounds on the first $O(logn)$ levels is sufficient to recover the seed length in [CHHL19], 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 emph{level-k unsigned Fourier sum}, which is potentially a much smaller quantity than the $L_1$ notion in previous works. By generalizing a connection established in [CHH+20], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for $mathbb{F}_2$ polynomials with seed length close to the state-of-the-art construction due to Viola [Vio09], which was not known to be possible using this framework.

Cited in

(4)

• Comparison of random number generators via Fourier transform
• Fourier bounds and pseudorandom generators for product tests
• Paradigms for Unconditional Pseudorandom Generators
• Pseudorandomness, symmetry, smoothing: I

This page was built for publication: Fractional pseudorandom generators from any fourier level

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115362)