On Sums of INW Pseudorandom Generators

William M. Hoza, Zelin Lv

TL;DR

This paper explores a new method for constructing pseudorandom generators (PRGs) that can fool complex computational tasks, specifically read-once branching programs (ROBPs). The authors show that XORing multiple instances of the INW PRG can achieve this goal, offering a new perspective on derandomization for space-bounded computation.

What Problem Does This Paper Address?

The core problem this paper tackles is the construction of efficient pseudorandom generators (PRGs) that can fool "constant-width read-once branching programs" (ROBPs). ROBPs are a model of computation relevant to space-bounded algorithms. While it's known that PRGs with seed lengths of $O(\log n)$ can fool ROBPs of width 3, achieving this for wider ROBPs or with better seed length bounds has been a significant challenge. The paper investigates whether combining existing PRGs, specifically the Impagliazzo-Nisan-Wigderson (INW) generator, through bitwise XORing can lead to improved PRGs for this task. They also explore the limitations of such XOR-based constructions.

Methods

The paper's primary contribution is the analysis of "sums of INW generators," specifically the bitwise XOR of multiple INW PRGs. The authors leverage the concept of "unpredictability" and draw inspiration from "Yao's XOR Lemma" from circuit complexity.

Key techniques include:

  • INW Generator Construction: The paper builds upon the recursive construction of the INW generator, which uses expander graphs at each step.
  • XORing Generators: The core idea is to construct a new generator by taking the bitwise XOR of $t$ independent INW generators.
  • Spectral Expansion Analysis: The analysis heavily relies on the spectral expansion properties of the expander graphs used in the INW construction.
  • Robust PRG Definition: A crucial technical tool is the definition of a "robust PRG," which is a multi-seed PRG that remains effective even when some seeds are fixed. This allows for inductive proofs.
  • Lower Bound Techniques: For proving limitations, the authors employ techniques that analyze the structure of the generated pseudorandomness and its ability to fool specific functions (distinguishers).

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • XORing INW Generators Works (to an extent): The paper demonstrates that XORing $t$ copies of INW generators, even with relatively "mild" expander graphs, can fool constant-width ROBPs. This provides a new way to achieve a known seed length bound.
  • Intrinsic Limitations of XORing: A significant finding is that no matter how many INW generators are XORed or how expansion parameters are set, if the proof of correctness relies solely on spectral expansion properties, the seed length will inevitably be $\Omega(\log^2 n)$ for fooling width-3 ROBPs. This suggests that spectral expansion alone is not sufficient for achieving optimal seed lengths for wider ROBPs using this approach.
  • Incomparability of Approaches: The paper shows that increasing the number of XORed generators ($t$) and using a single generator with a "stronger" expander graph (smaller $\lambda$) are not always interchangeable. There are scenarios where one approach is better than the other, highlighting the nuanced nature of PRG construction.
  • "Step 1" of a Proposed Strategy: The positive result (Theorem 7) achieves "Step 1" of a proposed two-step strategy for constructing near-optimal PRGs: proving that XORing INW generators fools ROBPs. "Step 2" (derandomizing this proof) remains an open challenge.

Key Results

  • Theorem 7: An explicit PRG constructed by XORing $t$ INW generators fools width-$w$ ROBPs with error $\frac{t \log n}{n \log(w+1)} \prod_{i=1}^t \sum_{j=1}^{\log n} \lambda_{i,j}$. This implies a PRG with seed length $O(\log^2 n \cdot \log w + \log n \cdot \log(1/\varepsilon))$ for constant width, re-proving a known bound.
  • Theorem 8: If any PRG in the family $INW^{\oplus t}(\Lambda)$ fools width-3 ROBPs with error 0.99, then every PRG in that family has a seed length of $\Omega(\log^2 n)$. This is a fundamental limitation of the XOR-of-INW approach.
  • Theorem 9 & 10: These theorems establish the incomparability between using multiple XORed INW generators versus using a single INW generator with stronger expander graphs, showing that neither approach universally dominates the other.

Limitations and Future Work

  • Derandomization Challenge: The paper's proposed two-step strategy for constructing near-optimal PRGs for ROBPs is only partially realized. While "Step 1" (proving that XORing INW generators works) is achieved, "Step 2" (derandomizing this proof, i.e., showing it works even with pseudorandom seeds) remains an open problem.
  • Optimal Dependence on Width: The authors pose the question of whether the dependence on the width $w$ in Theorem 7 can be improved from $O(\log^2 n \cdot \log w)$ to something like $poly(n, w)$.
  • General XOR Lemma: The paper suggests that a general "XOR lemma" for unpredictability in bounded-width ROBPs could be key to future progress, particularly for derandomization.
  • Extractor-Based Constructions: The authors note that an alternative construction of INW-like generators using extractors instead of expanders might be more amenable to derandomization, though it's unclear how to apply their current proof techniques to such constructions.

Summary updated

BibTeX
@inproceedings{hoza2025sums,
  author = {William M. Hoza and Zelin Lv},
  title = {{On Sums of INW Pseudorandom Generators}},
  booktitle = {APPROX/RANDOM},
  year = {2025},
  doi = {10.4230/lipics.approx/random.2025.67},
}
Figure