Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs

DOI10.1007/978-3-030-89543-3_1OpenAlexW3208154583MaRDI QIDQ2695266

Edward Pyne, Salil P. Vadhan

Publication date: 30 March 2023

Full work available at URL: https://doi.org/10.1007/978-3-030-89543-3_1

zbMATH Keywords

spectral graph theorypseudorandomnessspace-bounded computation

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Paradigms for Unconditional Pseudorandom Generators

Cites Work

• Unnamed Item
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Pseudorandom generators for space-bounded computation
• Randomness is linear in space
• Pseudorandomness for network algorithms
• On the Power of the Randomized Iterate
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Algorithmic derandomization via complexity theory
• Undirected connectivity in log-space
• Tiny families of functions with random properties: A quality-size trade-off for hashing
• Pseudorandom generators for width-3 branching programs
• Hitting sets with near-optimal error for read-once branching programs
• Pseudorandom generators for group products
• Using Nondeterminism to Amplify Hardness
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Error reduction for weighted PRGs against read once branching programs

This page was built for publication: Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs