Fractional Pseudorandom Generators from Any Fourier Level

Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty

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:

  1. 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$.
  2. 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

Abstract

We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2019] that exploit L₁ 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 [Chattopadhyay et al., 2019], or have polynomial dependence on the error parameter in the seed length [Eshan Chattopadhyay et al., 2019], and thus answers an open question in [Eshan Chattopadhyay et al., 2019]. 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 [Chattopadhyay et al., 2019], 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₁ notion in previous works. By generalizing a connection established in [Chattopadhyay et al., 2020], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for 𝔽₂ polynomials with seed length close to the state-of-the-art construction due to Viola [Emanuele Viola, 2009].
BibTeX
@inproceedings{chattopadhyay2021fractional,
  author = {Eshan Chattopadhyay and Jason Gaitonde and Chin Ho Lee and Shachar Lovett and Abhishek Shetty},
  title = {{Fractional Pseudorandom Generators from Any Fourier Level}},
  booktitle = {CCC},
  year = {2021},
  url = {https://openreview.net/forum?id=tXgyh19tlit},
}

Loading related content...

Figure