2026-07-23T04:27:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14284 2024-03-06T10:53:52Z ddc:004 open_access

Fractional Pseudorandom Generators from Any Fourier Level Chattopadhyay, Eshan Gaitonde, Jason Lee, Chin Ho Lovett, Shachar Shetty, Abhishek Derandomization pseudorandomness pseudorandom generators Fourier analysis 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eshan Chattopadhyay and Jason Gaitonde and Chin Ho Lee and Shachar Lovett and Abhishek Shetty 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.10 urn:nbn:de:0030-drops-142843 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.10 eng https://creativecommons.org/licenses/by/4.0/legalcode