Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
From MaRDI portal
Publication:6623584
DOI10.1007/s00453-024-01251-2MaRDI QIDQ6623584
William M. Hoza, Salil Vadhan, Edward Pyne
Publication date: 24 October 2024
Published in: Algorithmica (Search for Journal in Brave)
Cites Work
- Unnamed Item
- 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
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
- Pseudorandom Generators for Regular Branching Programs
- 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
- Random Cayley graphs and expanders
- Tiny families of functions with random properties: A quality-size trade-off for hashing
- Explicit, almost optimal, epsilon-balanced codes
- Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs
- Pseudorandom generators for width-3 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
