Abstract
Pseudorandom generators are constructed which convertO(SlogR) truly random bits toR bits that appear random to any algorithm that runs inSPACE(S). In particular, any randomized polynomial time algorithm that runs in spaceS can be simulated using onlyO(Slogn) random bits. An application of these generators is an explicit construction of universal traversal sequences (for arbitrary graphs) of lengthn O(logn).
The generators constructed are technically stronger than just appearing random to spacebounded machines, and have several other applications. In particular, applications are given for “deterministic amplification” (i.e. reducing the probability of error of randomized algorithms), as well as generalizations of it.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, andC. Rackoff: Random walks, universal sequences and the complexity of maze problems, in:20 th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1979, 218–223.
M. Ajtai, J. Komlós, andE. Szemerédi: Deterministic simulation in logspace, In:Proceedings of the 19 th Annual ACM Symposium on Theory of Computing, New York City, 1987, 132–141.
M. Ajtai andA. Wigderson: Deterministic simulation of probabilistic constant depth circuits, In:26 th Annual Symposium on Foundations of Computer Science, Portland, Oregon, 1985, 11–19.
M. Blum andS. Micali: How to generate cryptographically strong sequences of pseudo-random bits,SIAM J. Comp.,13, (1984) 850–864.
L. Babai, N. Nisan, andM. Szegedy: Multiparty protocols and logspace-hard pseudorandom sequences, In:Proceedings of the 21 st Annual ACM Symposium on Theory of Computing, Seattle, Washington, 1989, 1–11.
B. Chor andO. Goldreich: On the power of two points biased sampling, Manuscript, 1986.
L. Carter andM. Wegman: Universal hash functions,J. Comp. and Syst. Sci. 18, (1979) 143–154.
A. Cohen andA. Wigderson: Dispersers, deterministic amplification, and weak random sources, In:30 th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, 1989, 14–19.
R. Impagliazzo, L. Levin, andM. Luby: Pseudorandom generation from oneway functions, In:Proceedings of the 21 st Annual ACM Symposium on Theory of Computing, Seattle, Washington, 1989, 12–24.
S. Istrail: Polynomial traversing sequences for cycles are constructable, In:Proceedings of the 20 th Annual ACM Symposium on Theory of Computing, 1988, 491–503.
R. Impagliazzo andD. Zuckerman: How to recycle random bits, In:30 th Annual Symposium on Foundations of Computer Science, Reseach Triangle Park, NC, 1989, 248–253.
R. Karp, N. Pippenger, andM. Sipser: A time-randomness tradeoff, In:AMS Conference on Probabilistic Computational Complexity, 1985.
H. Karloff, R. Paturi, andJ. Simon: Universal sequences of lengthn O(logn) for cliques,Inf. Proc. Let. 28, (1988) 241–243.
Y. Mansour, N. Nisan, andP. Tiwari: The computational complexity of universal hashing, In:Proceedings of the 22 nd Annual ACM Symposium on Theory of Computing, 1990, 235–243.
N. Nisan andA. Wigderson: Hardness vs. randomness, In:29 th Annual Symposium on Foundations of Computer Science, White Plains, New York, 1988, 2–12.
M. O. Rabin: Probabilistic algorithm for testing primality,J. of Number Theory 12, (1980) 128–138.
M. Santha: On using deterministic functions to reduce randomness in probabilistic algorithms, Manuscript, 1986.
M. Sipser: Expanders, randomness or time vs. space,JCSS 36 (1988), 379–383.
U. Vazirani: Efficiency considerations in using semi-random sources, In:Proceedings of the 19 th Annual ACM Symposium on Theory of Computing, New York City, 1987, 160–168.
A. C. Yao: Theory and applications of trapdoor functions, In:23 rd Annual Symposium on Foundations of Computer Science, 1982, 80–91.
Author information
Authors and Affiliations
Additional information
This work was done in the Laboratory for Computer Science, MIT, supported by NSF 865727-CCR and ARO DALL03-86-K-017
Rights and permissions
About this article
Cite this article
Nisan, N. Pseudorandom generators for space-bounded computation. Combinatorica 12, 449–461 (1992). https://doi.org/10.1007/BF01305237
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01305237