How strong is Nisan's pseudo-random generator?
From MaRDI portal
Publication:1944139
DOI10.1016/j.ipl.2011.04.013zbMath1260.68283MaRDI QIDQ1944139
Matei David, Anastasios Sidiropoulos, Periklis A. Papakonstantinou
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2011.04.013
65C10: Random number generation in numerical analysis
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Pseudo-random graphs and bit probe schemes with one-sided error, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
Cites Work
- Unnamed Item
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- Pseudorandom generators for space-bounded computation
- On read-once vs. multiple access to randomness in logspace
- Pseudorandomness for network algorithms
- Fast parallel matrix and GCD computations
- Computational Complexity