TL;DR
This paper expands the polarizing random walk framework for constructing pseudorandom generators (PRGs), showing that Fourier bounds at any intermediate level $k \ge 3$ suffice to construct PRGs whose seed quality smoothly scales with $k$. Crucially, their analysis relies only on the level-$k$ unsigned Fourier sum (a potentially much smaller quantity than standard $L_1$ bounds) and connects PRG design directly to Taylor approximations on subcubes and correlation bounds.
What Problem Does This Paper Address?
In derandomization, the goal is to design pseudorandom generators (PRGs) that fool classes of Boolean functions while using as few truly random bits (the seed length) as possible. A powerful recent paradigm—the polarizing random walk framework—builds PRGs by first constructing "fractional" PRGs (which output continuous values in $[-1, 1]^n$) and then walking them toward the Boolean hypercube $\{-1, 1\}^n$.
However, previous applications of this framework sat at two inconvenient extremes:
- They required Fourier bounds across the entire tail of the function spectrum (all levels $1 \le k \le n$) to get polylogarithmic dependence on the error parameter $\varepsilon$.
- Or, they relied only on level-2 Fourier bounds, but suffered an exponentially worse (polynomial) dependence on $1/\varepsilon$ in the seed length.
This left a central open question: Can we interpolate between these extremes using Fourier bounds up to an intermediate level $k$, and can we relax the stringent $L_1$ Fourier mass requirements to weaker, more manageable quantities?
Methods
The authors introduce an alternate analysis of fractional PRGs rooted in polynomial approximation and real analysis:
- Taylor’s Theorem on Multilinear Extensions: Rather than analyzing Fourier tails directly, the authors consider one-dimensional restrictions $g(t) = f(tx)$ of the multilinear extension of $f \in \mathcal{F}$. Applying Taylor’s theorem with a Lagrange remainder term, all high-degree terms "collapse" into a single $k$-th derivative evaluated at an intermediate point.
- Bounding the Remainder via Random Restrictions: To evaluate derivatives away from zero, they use a "recentering" trick: intermediate points are expressed as expectations over random restrictions. Because the function class $\mathcal{F}$ is closed under restrictions, this keeps the function inside the convex hull of $\mathcal{F}$.
- Unsigned Fourier Bounds ($M_k$): The analysis only requires bounds on the level-$k$ absolute Fourier sum $M_k(\mathcal{F}) = \max_{x \in \{-1,1\}^n} |\sum_{|S|=k} \hat{f}(S)x^S|$, which is bounded above by (and often much smaller than) the classical $L_1$ Fourier mass $L_{1,k}(\mathcal{F}) = \sum_{|S|=k} |\hat{f}(S)|$.
- Approximations on Subcubes: The authors prove that low-degree Fourier truncations uniformly approximate Boolean functions on scaled subcubes $[-c, c]^n$ for $c \approx (\varepsilon / M_k(\mathcal{F}))^{1/k}$, and show this is near-optimal via Chebyshev polynomials.
Datasets
Not discussed in the paper. (This is a theoretical work in computational complexity and does not use empirical datasets.)
Key Insights and Ideas
- Fourier Truncation as Local $L_\infty$ Approximation: While Parseval's identity shows low-degree Fourier expansion is the optimal $L_2$-approximator over $\{-1, 1\}^n$, it also acts as a near-optimal uniform ($L_\infty$) approximator over small neighborhoods $[-c, c]^n$ around the origin.
- $M_k(\mathcal{F})$ is Easier than $L_{1,k}(\mathcal{F})$: When a function class is closed under input negation, $M_k(\mathcal{F})$ corresponds to an unsigned Fourier sum. Bounding this sum reduces directly to proving correlation/covariance bounds against XORs of shifted majority functions, linking PRGs to well-studied correlation lower bounds.
- Why $k \ge 3$ Matters: For $k=1$ or $k=2$, the variance of the fractional generator does not scale sublinearly with error $\varepsilon$. Composing independent steps in the random walk gadget accumulates too much error unless $k > 2$.
Key Results
-
Smooth Interpolation (Theorem 4 & 27): Assuming $M_k(\mathcal{F}) \le b^k$ for $k \ge 3$, there is an explicit PRG with seed length: $$O\left(\frac{b^{2 + 4/(k-2)} \cdot k \log n \cdot \log^{1 + 2/(k-2)}(n/\varepsilon)}{\varepsilon^{2/(k-2)}}\right)$$ If $L_{1, i}(\mathcal{F}) \le b^i$ bounds also hold for all $i < k$, the seed length improves to $O(b^2 \cdot \text{polylog}(n/\varepsilon))$ whenever $\varepsilon \ge b \log n \cdot 2^{-O(k)}$. For $\varepsilon = 1/\text{poly}(n)$, bounds only up to level $k = \Theta(\log n)$ suffice to recover the full-tail seed length.
-
Low-Degree $\mathbb{F}_2$ Polynomials (Theorem 30): Known Fourier bounds for degree-$d$ polynomials over $\mathbb{F}_2$ were previously insufficient for polarizing random walks due to blowing up at higher levels. Using their level-$k$ analysis with $k = \Theta(\log(\log(n)/\varepsilon))$, the authors construct an explicit PRG for degree-$d$ polynomials over $\mathbb{F}_2$ with seed length: $$2^{O(d)} \cdot \log^3(\log(n)/\varepsilon) \cdot \log(n/\varepsilon)$$ This achieves polylogarithmic dependence on $n/\varepsilon$, bringing the polarizing walk framework close to Viola's benchmark construction ($d \log n + O(d 2^d \log(1/\varepsilon))$).
Limitations and Future Work
- The $k = 1, 2$ Barrier: The Taylor-expansion technique cannot generate PRGs using only level-2 $M_2$ bounds (it polarizes trivially to $\pm 1$ without fooling functions). Extending $M_2$-only bounds to PRGs remains open.
- Superlogarithmic Degree $\mathbb{F}_2$ Polynomials: Like Viola's generator, this construction does not achieve non-trivial results for degree $d = \Omega(\log n)$. However, the authors conjecture that bounding $M_k(\mathcal{F}) \le (\text{poly}(k, \log n) \cdot 2^{o(d)})^k$ even just at $k = 3$ would break this logarithmic barrier and yield PRGs for $\mathrm{AC}^0[\oplus]$.
- Refining Assumptions: A remaining question is whether one can obtain the improved seed length using level bounds $M_i(\mathcal{F}) \le b^i$ for all $i \le k$, rather than requiring the stronger $L_{1,i}$ bounds on the lower levels.
Summary updated