Fractional Pseudorandom Generators from Any Fourier Level

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

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

Abstract

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 [CHLT10], 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.
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},
}
Figure