Fractional Pseudorandom Generators from the $k$th Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Abhishek S. Shetty · arXiv (Cornell University) · 2020
In recent work by [CHHL19, CHLT19], the authors exhibit a flexible construction of pseudorandom generators for classes of that satisfy $L_1$ Fourier bounds. [CHHL19] show that if a class satisfies such tail bounds at all levels, this implies a PRG through their random walk framework that composes together fractional PRGs that polarize quickly to the Boolean hypercube. [CHLT19] show by derandomizing the analysis of [RT19] that just level-two Fourier bounds suffice to construct a PRG but 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 PRG, 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. We partially answer an open question by [CHLT19] that nearly interpolates between them. 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 state-of-the-art. We hope that this alternate analysis will be fruitful in improving the understanding of this new and powerful framework.