Fractional pseudorandom generators from any Fourier level

We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [4, 6] that exploit L1 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 [4], or have polynomial dependence on the error parameter in the seed length [6], and thus answers an open question in [6]. 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 [4], 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 L1 notion in previous works. By generalizing a connection established in [5], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for F2 polynomials with seed length close to the state-of-the-art construction due to Viola [26].

Duke Scholars

Author Jason Gaitonde Fuqua School of Business