摘要: Pseudorandom generators are constructed which convertO(SlogR) truly random bits toR that appear to any algorithm runs inSPACE(S). In particular, randomized polynomial time in spaceS can be simulated using onlyO(Slogn) bits. An application of these is an explicit construction universal traversal sequences (for arbitrary graphs) lengthnO(logn).
acm.org
springer.com
sci-hub.se 参考文章(18)
N. Nisan, A. Wigderson, Hardness vs. randomness [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science. pp. 2- 11 ,(1988) , 10.1109/SFCS.1988.21916
Michael O Rabin, Probabilistic algorithm for testing primality Journal of Number Theory. ,vol. 12, pp. 128- 138 ,(1980) , 10.1016/0022-314X(80)90084-0
Y. Mansour, N. Nisan, P. Tiwari, The computational complexity of universal hashing symposium on the theory of computing. pp. 235- 243 ,(1990) , 10.1145/100216.100246
A. Cohen, A. Wigderson, Dispersers, deterministic amplification, and weak random sources foundations of computer science. pp. 14- 19 ,(1989) , 10.1109/SFCS.1989.63449
Sorin Istrail, Polynomial universal traversing sequences for cycles are constructible symposium on the theory of computing. pp. 491- 503 ,(1988) , 10.1145/62212.62260
U. Vazirani, Efficiency considerations in using semi-random sources symposium on the theory of computing. pp. 160- 168 ,(1987) , 10.1145/28395.28413
J.Lawrence Carter, Mark N. Wegman, Universal classes of hash functions Journal of Computer and System Sciences. ,vol. 18, pp. 143- 154 ,(1979) , 10.1016/0022-0000(79)90044-8
Miklos Santha, On using deterministic functions to reduce randomness in probabilistic algorithms Information & Computation. ,vol. 74, pp. 241- 249 ,(1987) , 10.1016/0890-5401(87)90023-X
R. Impagliazzo, L. A. Levin, M. Luby, Pseudo-random generation from one-way functions Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89. pp. 12- 24 ,(1989) , 10.1145/73007.73009
Howard J. Karloff, Ramamohan Paturi, Janos Simon, Universal traversal sequences of length n O (log n ) for cliques Information Processing Letters. ,vol. 28, pp. 241- 243 ,(1988) , 10.1016/0020-0190(88)90197-4