Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs

Thomas Steinke, Salil P. Vadhan, Andrew Wan

TL;DR

This paper introduces a new pseudorandom generator for a specific type of computational model called width-3 branching programs. The generator achieves a significantly shorter seed length (O~(log³n)) compared to previous methods, bringing us closer to optimal pseudorandomness for space-bounded computation. This is achieved through a novel analysis of the "Fourier growth" of these branching programs.

What Problem Does This Paper Address?

The core problem this paper tackles is the construction of "optimal" pseudorandom generators for space-bounded computation. Specifically, they aim to create a generator that takes a short random seed (logarithmic in the output length) and produces a sequence of bits that looks random to any algorithm using only a logarithmic amount of space. This is a long-standing goal in theoretical computer science, with implications for derandomization (removing randomness from algorithms) and other areas like streaming algorithms.

A key challenge is that existing pseudorandom generators often rely on the order in which input bits are processed. This paper focuses on "oblivious" branching programs, where the input bits can be read in any order, making them harder to fool. Previous best constructions for this model had a seed length that was polynomial in n (specifically, n¹/²⁺ᵒ⁽¹⁾). The authors aim to improve this significantly.

Methods

The paper's main technical contribution is a new bound on the "Fourier growth" of width-3, oblivious, read-once branching programs. Fourier analysis is a powerful tool for understanding boolean functions. The "Fourier mass" of a function, particularly at specific "levels" (related to the number of input bits influencing a Fourier coefficient), measures its complexity.

The authors prove that for any width-3 branching program, the sum of the absolute values of its Fourier coefficients at level k is bounded by n² * (O(log n))*k. This bound is crucial because it's significantly better than what was previously known for this model and allows them to leverage existing techniques (from Reingold, Steinke, and Vadhan) to construct their pseudorandom generator.

The proof of this Fourier growth bound involves a clever reduction strategy:

  1. Random Restriction: They use random restrictions to simplify the problem. By randomly fixing some input bits, they can reduce the complexity of the branching program.
  2. Width Reduction: They show how to reduce the problem from width-3 branching programs to width-2 branching programs. This is a key step because width-2 branching programs are better understood and their "mixing" properties (how they distribute probabilities) are more tractable.
  3. Mixing Analysis: The analysis of width-2 programs relies on understanding their "mixing" behavior. They introduce a measure of mixing and show how it relates to Fourier mass.

The pseudorandom generator itself is based on a construction by Gopalan et al. [17] and Reingold et al. [32], but the novel Fourier growth bound is what enables its improved performance for width-3 branching programs.

Datasets

Not discussed in the paper. The paper deals with theoretical constructs (branching programs) rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Fourier Growth as a Key to Pseudorandomness: The paper highlights that understanding the Fourier spectrum of computational models is critical for constructing pseudorandom generators. A tighter bound on Fourier growth directly translates to a better generator.
  • Width-3 is a Critical Threshold: The difficulty of fooling width-3 branching programs compared to width-2 programs is emphasized. The techniques developed here specifically address this jump in complexity.
  • Random Restrictions as a Powerful Tool: The paper demonstrates the effectiveness of random restrictions in simplifying complex computational models, allowing for analysis using techniques developed for simpler cases.
  • "Mixing" is Fundamental: The concept of how a branching program "mixes" input distributions is central to the analysis, particularly for width-2 programs. The paper explores this notion and its connection to Fourier analysis.
  • Tightness of the Bound: The authors show that their bound on Fourier growth is nearly tight, up to a logarithmic factor, suggesting that their analysis captures the essential complexity of width-3 branching programs.

Key Results

  • Pseudorandom Generator for Width-3 Branching Programs: The paper presents an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs with a seed length of O~(log³n).
  • Improved Seed Length: This is a significant improvement over the previous best seed length of n¹/²⁺ᵒ⁽¹⁾ for this model.
  • New Fourier Growth Bound: A novel bound is established for the Fourier growth of width-3 branching programs: for any such program f and any k, the sum of |f̂(s)| over all s with |s|=k is at most n² * (O(log n))*k.
  • Generalization: The work generalizes a previous result for permutation branching programs to the broader class of width-3 branching programs.

Limitations and Future Work

  • Seed Length vs. Optimal: While the seed length of O~(log³n) is a significant improvement, it is still far from the theoretically optimal O(log n). Further improvements would likely require new techniques, possibly involving "sandwiching polynomials" or modifying the generator's recursive structure.
  • Extending to Higher Widths (w > 3): The current techniques face significant obstacles when trying to extend them to width-4 and beyond. A key issue is that the measure of "mixing" used for width-2 programs (λ(D)) can exceed 1 for widths greater than 2, making the analysis more complex. The authors suggest the need for a better notion of mixing that captures both the mixing property and the effect of random restrictions.
  • Proof Complexity: The paper notes that the proof is split into two parts and would benefit from a more unified approach.
  • Relaxing Fourier Growth: The authors suggest that relaxing the Fourier growth condition to "sandwiching polynomials" might lead to better results, as seen in other areas of pseudorandomness.

Summary updated

Abstract

We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ). The previously best known seed length for this model is n^{1/2+o(1)} due to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM'13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f : {0,1}^n -> {0,1} computed by such a branching program, and k in [n], sum_{|s|=k} |hat{f}(s)| < n^2 * (O(\log n))^k, where f(x) = sum_s hat{f}(s) (-1)^<s,x> is the standard Fourier transform over Z_2^n. The base O(log n) of the Fourier growth is tight up to a factor of log log n.
BibTeX
@inproceedings{steinke2014pseudorandomness,
  author = {Thomas Steinke and Salil P. Vadhan and Andrew Wan},
  title = {{Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs}},
  booktitle = {Theory Comput},
  year = {2014},
  url = {https://openreview.net/forum?id=9CVxKSciYKQ},
}
Figure