Near-Optimal Pseudorandom Generators for Bounded Computational Models

37 concepts17 papers3 proposals

The foundational quest of derandomization is to prove that randomness does not fundamentally add computational power. In complexity theory, this translates to showing that classes like $BPP$ (problems solvable in randomized polynomial time) and $BPL$ (problems solvable in randomized logarithmic space) are equal to their deterministic counterparts, $P$ and $L$.

To eliminate randomness deterministically, we use a Pseudorandom Generator (PRG). A PRG takes a short, truly random string of bits—the seed—and stretches it into a much longer sequence that appears completely random to a specific class of algorithms. If we can reduce the required seed length to a logarithmic scale ($O(\log n)$), we can deterministically simulate the randomized algorithm by cycling through all possible short seeds and taking a majority vote.

Achieving this goal requires designing PRGs that are optimal or near-optimal. Recent research has converged on breaking long-standing efficiency bottlenecks for two primary types of bounded computational models: Read-Once Branching Programs (ROBPs), which model space-bounded computation, and $AC^0$ circuits, which model constant-depth parallel computation.


Breaking the Space-Bounded Bottleneck via Fourier Analysis

To fool space-bounded randomized algorithms, researchers analyze Read-Once Branching Programs (ROBPs). Think of an ROBP as a streaming algorithm with a strict memory limit. As it reads an input bit by bit, it transitions between a bounded number of internal states (the width $w$ of the program).

For nearly thirty years, Nisan’s classic PRG stood as the state-of-the-art for space-bounded derandomization, but it carried a seed length bottleneck of $O(\log^2 n)$. For narrow programs, such as width-3 ROBPs, this quadratic exponent felt highly suboptimal. Why should an algorithm with such tiny memory require so much randomness to fool?

The breakthrough came from shifting the perspective toward Fourier growth bounds. If we treat the branching program as a real-valued function, we can decompose it into Fourier coefficients. If the high-frequency Fourier coefficients decay rapidly, it means the program is structurally incapable of detecting fine-grained, high-frequency correlations. Consequently, a PRG only needs to match the low-frequency components of true randomness to successfully fool the program.

[Short Seed] ---> [ PRG ] ---> [ Pseudorandom Bits ] ---> [ Bounded Model (ROBP / AC0) ]
                                                                 |
                                      Fourier Decay / Switching Lemmas ensure the model
                                      cannot distinguish these from truly random bits.

Using this approach, Thomas Steinke et al. demonstrated in Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs (and its parallel edition Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs) that the Fourier growth of width-3 ROBPs is tightly bounded. This structural insight allowed them to bypass the polynomial seed length barriers of older methods. Building directly on this framework, Raghu Meka et al. in Pseudorandom Generators for Width-3 Branching Programs successfully collapsed the seed length to a near-optimal $\tilde{O}(\log n)$, effectively breaking the $O(\log^2 n)$ barrier.

This Fourier-analytic toolkit also applies to structural variants where states do not collapse. In a permutation branching program, each layer's transitions form a bijection, meaning the program never discards information about its state. Omer Reingold et al. leveraged this property in Pseudorandomness for Regular Branching Programs via Fourier Analysis to optimize seed lengths for regular and permutation models. Pushing this boundary to its logical extreme, Edward Pyne et al. established near-optimal seed lengths in Pseudorandom Generators for Unbounded-Width Permutation Branching Programs, proving that if the permutation structure is preserved, the PRG can remain highly efficient regardless of the program's width.


The Hardness-to-Randomness Frontier in Bounded Depth

While ROBPs constrain memory, $AC^0$ circuits (constant-depth circuits with unbounded fan-in) constrain parallel time. Designing PRGs for $AC^0$ circuits relies on the hardness-to-randomness paradigm: if a circuit class is fundamentally incapable of computing a specific hard function, that function can be repurposed to construct a PRG that fools the entire class.

Because of this paradigm, a PRG's efficiency is fundamentally bottlenecked by our ability to prove circuit lower bounds. A PRG is considered "optimal relative to hardness assumptions" if its seed length matches the mathematical limits imposed by our current understanding of circuit complexity.

The primary mechanism for proving these lower bounds—and constructing these PRGs—is the switching lemma. A switching lemma states that if you randomly restrict a subset of a circuit's variables (fixing them to 0 or 1), the remaining circuit simplifies dramatically, collapsing down into a shallow decision tree. To use this for derandomization, the restriction itself cannot be truly random; it must be generated pseudorandomly using a very short seed.

To bridge the gap to optimality, Li-Yang Tan et al. developed a novel "pseudorandom multi-switching lemma" in Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. By applying multiple rounds of pseudorandom restrictions simultaneously, the authors achieved PRG seed lengths that are essentially optimal given current circuit lower bounds. This technique was expanded by Rocco A. Servedio et al. in Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas to provide state-of-the-art hardness-to-randomness conversions for both $AC^0$ circuits and sparse $\mathbb{F}_2$ polynomials.

Finally, Xin Lyu closed the remaining mathematical overhead in Improved Pseudorandom Generators for AC0 Circuits. By pairing a fully-derandomized multi-switching lemma with a partitioning-based variable assignment strategy, the author designed a PRG with a seed length just a single $\log \log m$ factor away from the absolute theoretical lower bound.


The Core Mechanism: Iterative Pseudorandom Restrictions

Why do these modern PRGs achieve near-optimality where older, monolithic designs failed? The secret lies in the paradigm of iterative pseudorandom restrictions.

Instead of attempting to generate a single, massive pseudorandom string that fools a complex function all at once, the generator operates in sequential waves. This strategy, pioneered by Parikshit Gopalan et al. in Better Pseudorandom Generators from Milder Pseudorandom Restrictions, applies a "mild" pseudorandom restriction to the input variables at each step.

[Complex Function] 
       |
       v  (Apply Mild Pseudorandom Restriction 1) -> Requires tiny seed
[Simpler Function]
       |
       v  (Apply Mild Pseudorandom Restriction 2) -> Requires tiny seed
[Even Simpler Function]
       |
       v  ... repeat until trivial
[Constant Value (Fooled!)]

Each mild restriction fixes a small fraction of the variables while leaving the rest alive. Because the restriction is chosen pseudorandomly using a highly optimized, short-seed generator, it simplifies the target computational model (such as a read-once CNF or an ROBP) without destroying its core structural properties.

By repeating this process iteratively, the complex function gradually simplifies until it collapses into a trivial constant. The final seed length of the PRG is merely the sum of the tiny seeds used across all the iterative layers. This step-by-step simplification yields an efficiency that traditional monolithic architectures—such as the classic Impagliazzo-Nisan-Wigderson (INW) generator—cannot match under certain spectral limitations, as proven by William M. Hoza et al. in Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs.


Remaining Bottlenecks

While these strategies have successfully unlocked near-optimal seed lengths for structured models like width-3, regular, or monotone ROBPs (as explored by Dean Doron et al. in Pseudorandom Generators for Read-Once Monotone Branching Programs), scaling these results to general, wide ROBPs remains an open challenge.

As William M. Hoza notes in Better Pseudodistributions and Derandomization for Space-Bounded Computation, modern pseudorandom distributions face structural barriers when trying to maintain efficiency in low- or constant-error regimes. Furthermore, attempts to bypass these barriers by combining simpler generators—such as XORing multiple instances of the INW generator—still suffer from error bounds that scale poorly with the width of the branching program, a limitation detailed by Zelin Lv et al. in On Sums of INW Pseudorandom Generators.

Nevertheless, the tight structural relationships being uncovered—such as the reductions between hitting set generators and PRGs established by Dean Doron et al. in Implications of Better PRGs for Permutation Branching Programs and the width-independent hitting sets developed by Edward Pyne et al. in Hitting Sets for Regular Branching Programs—demonstrate that mastering these restricted models provides the exact mathematical foundation needed to eventually achieve full, unconditional derandomization.

Key Foundational Work

Better Pseudorandom Generators from Milder Pseudorandom Restrictions (2012) — contributed 3 concept elements to this direction.
Pseudorandomness for Regular Branching Programs via Fourier Analysis (2013) — contributed 2 concept elements to this direction.
Pseudorandom Generators for Combinatorial Shapes (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_hardness_to_randomness_conversio_8752f500,
  title = {optimal hardness-to-randomness conversion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-hardness-to-randomness-conversion/rdr_8752f500e67e425db25c25ce211ff56f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimal_hardness_to_randomness_conversio_8752f500_v1,
  title = {optimal hardness-to-randomness conversion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-hardness-to-randomness-conversion/rdr_8752f500e67e425db25c25ce211ff56f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake