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 [CHLT19], and thus answers an open question in [CHLT19]. 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 [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.
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 has polynomial dependence on the error parameter in the seed length [CHLT19], and thus answers an open question in [CHLT10]. 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 [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 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.
Improved main theorem. Additional result on constructing PRGs from correlation bounds.
In recent work by Chattopadhyay et al.[CHHL19,CHLT19], the authors exhibit a simple and flexible construction of pseudorandom generators for classes of Boolean functions that satisfy $L_1$ Fourier bounds. [CHHL19] show that if a class satisfies such tail bounds at all levels, this implies a PRG whose seed length depends on the quality of these bounds through their innovative random walk framework that composes together fractional PRGs that polarize quickly to the Boolean hypercube. On the other hand, [CHLT19] show that, by derandomizing the analysis of [RT19], just level-two Fourier bounds suffice to construct a pseudorandom generator using their framework; as this is a much weaker assumption on the class, [CHLT19] naturally obtain exponentially worse dependence on the error in the seed length compared to [CHHL19]. Moreover, this derandomization relies on simulating nearly independent Gaussians for the fractional pseudorandom generator, which necessitates the polynomial dependence on $1/\epsilon$ in each fractional step.
In this work, we attempt to bridge the gap between these two results. Namely, we partially answer an open question by [CHLT19] that nearly interpolates between them. In particular, we show that if one has bounds up to the level-$k$ $L_1$ Fourier mass of a closely related class of functions, where $k>2$, one can obtain improved seed length, the degree to which is determined by how high $k$ can be taken. Our analysis shows that for error $\epsilon=1/\text{poly}(n)$, one needs control at just level $O(\log n)$ to recover the seed length of [CHHL19], without assumptions on the entire tail. We avoid this by providing a simple, alternate analysis of their fractional PRG that instead relies on Taylor's theorem and $p$-biased Fourier analysis to avoid assumptions on the weights of the higher-order terms. This further allows us to show that this framework can handle the class of low-degree polynomials over $\mathbb{F}_2$, with slightly worse dependence than the current state-of-the-art, which was not previously known. We hope that this alternate analysis will be fruitful in improving the understanding of this new and powerful framework.
