TL;DR
This paper introduces a new pseudorandom generator (PRG) that can efficiently "fool" a specific type of computational model called monotone read-once branching programs (ROBPs). This is a significant step towards understanding and reducing the need for randomness in computation, with implications for circuit complexity and derandomization.
What Problem Does This Paper Address?
The paper tackles the challenge of constructing efficient pseudorandom generators (PRGs) for a class of computational models known as read-once branching programs (ROBPs). Specifically, they focus on monotone ROBPs, which have a structured property where the states at each step can be ordered. The ultimate goal in this area is to achieve PRGs with seed lengths that are optimal (logarithmic in the input size), a feat that has been elusive for many computational models. While previous work has achieved good results for related models (like permutation ROBPs), monotone ROBPs present a distinct challenge, and existing PRGs don't perform well on them. This work aims to bridge that gap by providing a PRG with a near-optimal seed length for these monotone ROBPs.
Methods
The authors employ an "iterated restrictions" approach, a common technique in PRG construction. This involves repeatedly applying pseudorandom "restrictions" to the input variables. Each restriction effectively fixes some input bits and simplifies the problem. The core of their method lies in two key observations for achieving width reduction:
- Realizing Collisions: They show that after a suitable restriction, a monotone branching program is likely to have a "collision" in one of its layers. A collision means multiple states map to the same next state, which effectively reduces the program's width.
- Alphabet Reduction: They also develop a technique to reduce the "alphabet" (the set of possible values for intermediate states) of the branching program. This is crucial for making subsequent restrictions more effective.
By iteratively applying these two techniques, they progressively reduce the width of the branching program until it becomes simple enough to be fooled by a standard PRG. The analysis leverages concepts like k-wise independent distributions and d-biased distributions to ensure the restrictions are "pseudorandom" enough to preserve the program's behavior.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Monotonicity as an "Opposite" Constraint: The paper highlights that the "monotone" property of these branching programs is, in a sense, the opposite of the "permutation" property studied in prior work. This suggests a broader understanding of how structural constraints on computational models impact PRG design.
- Width Reduction as a Key Strategy: The core insight is that by exploiting the structure of monotone ROBPs, one can iteratively reduce their "width" (a measure of their complexity) using pseudorandom restrictions. This is a powerful idea that could potentially be applied to other computational models.
- Alphabet Reduction Complements Width Reduction: The ability to reduce the alphabet size of intermediate states is shown to be a crucial companion to width reduction, enabling the iterative simplification process.
- Bridging the Gap to Optimal Seed Lengths: While not achieving the absolute optimal seed length, the paper makes significant progress by getting closer to the desired O(log n) seed length for a challenging class of computational models.
Key Results
The paper presents an explicit pseudorandom generator (PRG) that fools constant-width monotone read-once branching programs (ROBPs) with a seed length of $O(w^2 \log(n/\epsilon) \cdot (\log \log(n/\epsilon))^2)$, where $n$ is the number of input bits, $w$ is the width of the branching program, and $\epsilon$ is the error parameter. This is a significant improvement over previous results for this specific class of programs. They also show that monotone read-once ROBPs are strictly more powerful than read-once AC$^0$ circuits.
Limitations and Future Work
The authors acknowledge that their PRG's seed length, while improved, is not yet the theoretically optimal $O(\log n)$. They suggest that their techniques for width reduction and alphabet reduction, particularly the idea of exploiting collisions, could be useful for designing PRGs for other computational models and potentially for breaking the $O(\log n)$ barrier for general read-once branching programs. The paper also notes that their construction is for read-once monotone branching programs, and extending it to general (non-read-once) monotone branching programs would be a natural next step.
Summary updated