Abstract
We present new results on the polarizing random walk framework for constructing pseudorandom generators (PRGs), exploiting $L_1$ Fourier tail bounds for Boolean functions. By applying Taylor’s theorem to the Fourier expansion and bounding the degree-$k$ Lagrange remainder term through multilinearity and random restrictions, we show that bounds on the $k$-th level of the Fourier spectrum are sufficient to construct PRGs with seed lengths that scale gracefully with $k$. This approach interpolates between previous works that required bounds on all Fourier levels and those with poor error dependence. Furthermore, we introduce the "level-$k$ unsigned Fourier sum" ($M_k$) as a more efficient metric than standard $L_1$ notions. Finally, we demonstrate the framework's versatility by constructing a PRG for $\mathbb{F}_2$ polynomials, achieving seed lengths competitive with state-of-the-art methods.
Introduction
In the field of computational complexity, derandomization—the process of replacing randomized algorithms with deterministic counterparts—remains a fundamental challenge. The primary tool for this task is the Pseudorandom Generator (PRG), which expands a short, truly random seed into a longer sequence of bits that appears random to a specific class of functions.
Recent advancements have utilized the "polarizing random walk" framework to build PRGs based on Fourier tail bounds. This framework relies on the premise that if a function's high-frequency Fourier components have limited "energy," the function can be fooled by a structured random process. However, prior applications of this framework faced a significant limitation: they either required stringent bounds across the entire Fourier spectrum or suffered from exponential dependence on the error parameter when only the second Fourier level was controlled. This research addresses this gap by asking whether control over an arbitrary $k$-th level of the Fourier spectrum is sufficient for efficient PRG construction.
Methodology
Fractional PRGs and Taylor's Theorem
The authors refine the analysis of fractional PRGs—random variables taking values in the solid cube $[-1, 1]^n$. The core innovation involves treating the multilinear expansion of a Boolean function as a smooth function and applying Taylor’s theorem. They demonstrate that the low-degree portion of a Fourier expansion serves as an effective uniform approximator for the function within small "subcubes" near the origin.
Bounding the Lagrange Remainder
To manage the error in this Taylor approximation, the researchers employ a "random restriction" technique to bound the degree-$k$ Lagrange remainder term. This allows the PRG's error to be tied directly to the $k$-th level of the Fourier spectrum. This local approximation ensures that if a fractional PRG can "locally" fool the low-degree Taylor expansion, the resulting random walk will "globally" fool the target function.
The $M_k$ Quantity
A pivotal shift in this work is the move from the standard $L_1$ Fourier mass (the sum of absolute values of coefficients) to the "level-$k$ absolute Fourier sum," denoted as $M_k(\mathcal{F})$. This quantity is often significantly smaller and more analytically tractable than the $L_1$ norm. By focusing on $M_k$, the authors leverage tools from the study of resilient functions to improve PRG efficiency.
Correlation Bounds
Building on existing literature, the paper establishes a generalized reduction. It shows that the problem of constructing PRGs can be reduced to proving correlation bounds against "shifted majority" functions, providing a new pathway for derandomization research.
Key Results
General PRG Construction
The study proves that for any class $\mathcal{F}$ where the $k$-th Fourier level is bounded ($M_k(\mathcal{F}) \leq b^k$), a PRG can be constructed that avoids the exponential error blow-up characteristic of previous level-2 analyses.
Polylogarithmic Error Scaling
If Fourier bounds are available up to level $O(\log n)$, the framework achieves a seed length that is polylogarithmic in the inverse error ($1/\epsilon$). This matches the performance of the most efficient previous frameworks while requiring significantly weaker assumptions regarding the Fourier tail.
Application to $\mathbb{F}_2$ Polynomials
The framework successfully handles degree-$d$ polynomials over $\mathbb{F}_2$. The resulting PRG achieves a seed length of $2^{O(d)} \cdot \text{polylog}(n/\epsilon)$. While this is slightly behind the current state-of-the-art (Viola, 2009) in terms of its dependence on $\log n$, it demonstrates that the polarizing random walk framework is a viable and competitive approach for this classic problem—a result previously thought unattainable.
Discussion and Future Work
While the Taylor-based approach is powerful, it currently requires $k \geq 3$. It does not yet provide non-trivial improvements for cases where only the second Fourier level is bounded, leaving the construction by Chattopadhyay et al. (2019) as the standard for $k=2$.
Furthermore, the authors propose Conjecture 5.3, which suggests that specific bounds on $M_k$ for $\mathbb{F}_2$ polynomials could lead to a breakthrough PRG for the circuit class $AC^0[\oplus]$. Proving this conjecture remains a major open problem that could significantly advance our understanding of circuit complexity and derandomization.
Summary updated