How strong is Nisan's pseudo-random generator?

DOI10.1016/j.ipl.2011.04.013zbMath1260.68283OpenAlexW148806319MaRDI 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

zbMATH Keywords

computational complexityderandomizationNisan's pseudo-random generatorspace bounded

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (2)

On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ Pseudo-random graphs and bit probe schemes with one-sided error

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

This page was built for publication: How strong is Nisan's pseudo-random generator?