Pseudorandom Generators for Read-Once Monotone Branching Programs

DOI10.4230/LIPICS.APPROX/RANDOM.2021.58MaRDI QIDQ6090916zbMATH OpenOpenAlexFDO

Authors Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan

Publication date 20 November 2023

Full work available at URL https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.58

zbMATH Keywords

pseudorandom generatorsbranching programsconstant depth circuits

Mathematics Subject Classification ID

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

Recommendations

• Pseudorandom generators for regular branching programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Pseudorandom generators for width-3 branching programs
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Pseudorandomness for width-2 branching programs
• Pseudorandom Bits for Oblivious Branching Programs
• scientific article; zbMATH DE number 1962823
• Pseudorandomness for regular branching programs via Fourier analysis
• Near-optimal pseudorandom generators for constant-depth read-once formulas

Cited in

(7)

• Paradigms for Unconditional Pseudorandom Generators
• Pseudorandom Bits for Oblivious Branching Programs
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Approximating iterated multiplication of stochastic matrices in small space
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs

This page was built for publication: Pseudorandom Generators for Read-Once Monotone Branching Programs

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