Implications of better PRGs for permutation branching programs

DOI10.4230/LIPICS.APPROX/RANDOM.2025.28MaRDI QIDQ7346857zbMATH OpenFDO

Authors Dean Doron, William M. Hoza

Publication date 11 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2025.28

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• Better pseudorandom generators from milder pseudorandom restrictions
• Certified hardness vs. randomness for log-space
• Hitting sets for regular branching programs
• Hitting sets give two-sided derandomization of small space
• scientific article; zbMATH DE number 1301964 (Why is no real title available?)
• scientific article; zbMATH DE number 7701432 (Why is no real title available?)
• Title not available (Why is no real title available?)
• Improved algorithms via approximations of probability distributions
• Improved pseudorandom generators for depth 2 circuits
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• On the power of regular and permutation branching programs
• Paradigms for Unconditional Pseudorandom Generators
• Pseudodistributions that beat all pseudorandom generators (extended abstract)
• Pseudorandom generators for group products, extended abstract
• Pseudorandom generators for regular branching programs
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators for unbounded-width permutation branching programs
• Pseudorandom generators for width-3 branching programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandom walks on regular digraphs and the RL vs. L problem
• Pseudorandomness for network algorithms
• Pseudorandomness for width-2 branching programs
• Recursive error reduction for regular branching programs
• Simple optimal hitting sets for small-success RL
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• The coin problem and pseudorandomness for branching programs
• Weighted pseudorandom generators via inverse analysis of random walks and shortcutting

This page was built for publication: Implications of better PRGs for permutation branching programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346857)