Pseudorandomness for Linear Length Branching Programs and Stack Machines

DOI10.1007/978-3-642-32512-0_38MaRDI QIDQ3167416zbMATH OpenOpenAlexFDO

Authors Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan

Publication date 2 November 2012

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32512-0_38

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Pseudorandomness for width-2 branching programs
• Pseudorandom generators for regular branching programs
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandom Bits for Oblivious Branching Programs
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Pseudorandom bits and lower bounds for randomized Turing machines
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandom generators for width-3 branching programs
• On linear recursion and pseudorandomness
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs

Cited in

(8)

• Provable time-memory trade-offs: symmetric cryptography against memory-bounded adversaries
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Bounded independence plus noise fools products
• Pseudorandom Bits for Oblivious Branching Programs
• Pseudorandom bits and lower bounds for randomized Turing machines
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Pseudorandom Generators for Read-Once Monotone Branching Programs

This page was built for publication: Pseudorandomness for Linear Length Branching Programs and Stack Machines

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