Implications of Better PRGs for Permutation Branching Programs

Dean Doron, William M. Hoza

TL;DR

This paper explores the intricate relationship between pseudorandom generators (PRGs) and hitting set generators (HSGs) for a specific type of computational model called permutation branching programs. The authors demonstrate that improvements in PRGs for slightly more complex branching programs can lead to significant advancements in constructing HSGs for simpler, yet still challenging, branching programs. This work offers a new pathway to understanding fundamental complexity class relationships like L vs. BPL.

What Problem Does This Paper Address?

The paper tackles the long-standing challenge of "derandomizing" computation, specifically for constant-width standard-order read-once branching programs (ROBPs). Derandomization aims to replace the use of randomness in algorithms with deterministic procedures, often by constructing pseudorandom generators (PRGs). A key goal is to find PRGs that can "fool" these branching programs, meaning their output is statistically indistinguishable from truly random inputs.

While significant progress has been made for general branching programs, researchers have investigated models with additional structural restrictions, like "permutation" branching programs, to make headway. However, even for these restricted models, achieving PRGs with optimal seed lengths (related to computational efficiency) has been difficult, especially for low error rates. This paper bridges this gap by showing how improvements in PRGs for slightly larger width permutation programs can yield better HSGs for smaller width programs. HSGs are a relaxation of PRGs that are also crucial for derandomization and proving complexity class equalities like L = BPL.

Methods

The paper's core contribution lies in two main technical reductions:

  1. Fooling width-3 ROBPs via width-6 permutation programs: The authors show that if we have good PRGs for width-6 permutation programs, we can construct good PRGs for width-3 ROBPs. This is achieved by leveraging existing techniques that reduce the problem of fooling width-3 ROBPs to fooling "near-permutation" programs, and then showing how to adapt these to work with exact permutation programs of a slightly larger width. A key observation is that programs with a few "colliding layers" (deviations from the permutation property) can be decomposed into a sum of permutation programs.
  2. Converting PRGs for width-w to HSGs for width-(w+1): This is a more general reduction. The authors demonstrate that a PRG that fools width-w ROBPs with a certain error can be used to construct an HSG for width-(w+1) ROBPs. This involves a multi-step process:
  3. First, they show how to convert a PRG for width-w $\Lambda$-programs (a variant of ROBPs) into a hitting set for width-w $\Lambda$-programs.
  4. Then, they show how to combine hitting sets for $\Lambda$-programs and V-programs (another variant) to get a hitting set for width-(w+1) standard ROBPs.
  5. Finally, an error reduction technique is applied to obtain the desired low-error HSG.

The paper also introduces and utilizes concepts like $\Lambda$-programs and V-programs, which are useful for analyzing branching programs with early acceptance/rejection capabilities.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and relationships between computational models, rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Interplay between PRGs and HSGs: The paper highlights a strong connection between the power of PRGs for one class of programs and the effectiveness of HSGs for another. Specifically, better PRGs for slightly larger width permutation programs directly translate to better HSGs for smaller width programs.
  • Decomposition of "near-permutation" programs: A crucial insight is that programs deviating slightly from the strict permutation property (having "colliding layers") can be effectively decomposed into sums of exact permutation programs. This allows existing results on permutation programs to be leveraged.
  • Iterative construction of HSGs: The reduction from width-w PRGs to width-(w+1) HSGs is iterative. This suggests a potential path towards constructing HSGs for any constant width ROBP with very efficient seed lengths, although this remains speculative.
  • The importance of specific program models: The use of $\Lambda$-programs and V-programs, which allow for early acceptance/rejection, is instrumental in bridging the gap between different types of branching programs and in constructing the necessary hitting sets.

Key Results

The main theoretical results are:

  • Theorem 1.5: If there exist explicit PRGs for width-6 permutation ROBPs with error $1/n$ and seed length $O(\log n)$, then there exist explicit HSGs for width-4 ROBPs with error $1/\text{polylog}(n)$ and seed length $O(\log n)$. This is the paper's headline result.
  • Theorem 1.6: An explicit $\delta$-PRG for width-6 permutation programs implies an explicit $\varepsilon$-PRG for width-3 ROBPs. This improves upon prior work by Meka, Reingold, and Tal.
  • Theorem 1.7: An explicit PRG for width-w ROBPs with error $O(1/n)$ implies an explicit $\varepsilon$-HSG for width-(w+1) ROBPs with seed length $O(s + \log n \log(1/\varepsilon))$, where $s$ is the seed length of the original PRG.

Limitations and Future Work

  • Unweighted PRGs: The paper's reductions rely on unweighted PRGs. The authors note that if these reductions could be adapted to work with weighted PRGs (WPRGs), which have seen recent success, it could lead to even better HSGs for width-4 ROBPs.
  • Speculative Iteration: The authors speculate that their iterative reduction from width-w to width-(w+1) could potentially be extended to yield HSGs for all constant-width ROBPs with seed length $o(\log^2 n)$. This is presented as an exciting but speculative direction.
  • Constant Width Focus: The results are primarily focused on constant-width programs. Extending these to polynomial-width programs would be a significant challenge.
  • Explicit Constructions: While the paper proves the existence of certain generators, the focus is on explicit constructions, meaning they can be computed efficiently. The efficiency of these constructions (seed length) is a key metric.

Summary updated

BibTeX
@inproceedings{doron2025implications,
  author = {Dean Doron and William M. Hoza},
  title = {{Implications of Better PRGs for Permutation Branching Programs}},
  booktitle = {APPROX/RANDOM},
  year = {2025},
  doi = {10.4230/lipics.approx/random.2025.28},
}
Figure