{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:04:21Z","timestamp":1775282661009,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1992,12,1]],"date-time":"1992-12-01T00:00:00Z","timestamp":723168000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1992,12]]},"DOI":"10.1007\/bf01305237","type":"journal-article","created":{"date-parts":[[2005,3,25]],"date-time":"2005-03-25T10:20:39Z","timestamp":1111746039000},"page":"449-461","source":"Crossref","is-referenced-by-count":232,"title":["Pseudorandom generators for space-bounded computation"],"prefix":"10.1007","volume":"12","author":[{"given":"Noam","family":"Nisan","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lov\u00e1sz, 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.","DOI":"10.1109\/SFCS.1979.34"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, andE. Szemer\u00e9di: Deterministic simulation in logspace, In:Proceedings of the 19 th Annual ACM Symposium on Theory of Computing, New York City, 1987, 132?141.","DOI":"10.1145\/28395.28410"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/SFCS.1985.19"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum andS. Micali: How to generate cryptographically strong sequences of pseudo-random bits,SIAM J. Comp.,13, (1984) 850?864.","journal-title":"SIAM J. Comp."},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/73007.73008"},{"key":"CR6","unstructured":"B. Chor andO. Goldreich: On the power of two points biased sampling, Manuscript, 1986."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L. Carter","year":"1979","unstructured":"L. Carter andM. Wegman: Universal hash functions,J. Comp. and Syst. Sci. 18, (1979) 143?154.","journal-title":"J. Comp. and Syst. Sci."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/73007.73009"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/62212.62260"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"CR12","unstructured":"R. Karp, N. Pippenger, andM. Sipser: A time-randomness tradeoff, In:AMS Conference on Probabilistic Computational Complexity, 1985."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0020-0190(88)90197-4","volume":"28","author":"H. Karloff","year":"1988","unstructured":"H. Karloff, R. Paturi, andJ. Simon: Universal sequences of lengthn O(logn) for cliques,Inf. Proc. Let. 28, (1988) 241?243.","journal-title":"Inf. Proc. Let."},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/100216.100246"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"N. Nisan andA. Wigderson: Hardness vs. randomness, In:29 th Annual Symposium on Foundations of Computer Science, White Plains, New York, 1988, 2?12.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"M. O. Rabin","year":"1980","unstructured":"M. O. Rabin: Probabilistic algorithm for testing primality,J. of Number Theory 12, (1980) 128?138.","journal-title":"J. of Number Theory"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"M. Santha: On using deterministic functions to reduce randomness in probabilistic algorithms, Manuscript, 1986.","DOI":"10.1016\/0890-5401(87)90023-X"},{"key":"CR18","first-page":"379","volume":"36","author":"M. Sipser","year":"1988","unstructured":"M. Sipser: Expanders, randomness or time vs. space,JCSS 36 (1988), 379?383.","journal-title":"JCSS"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/28395.28413"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"A. C. Yao: Theory and applications of trapdoor functions, In:23 rd Annual Symposium on Foundations of Computer Science, 1982, 80?91.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01305237.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01305237\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01305237","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,7]],"date-time":"2021-07-07T10:38:33Z","timestamp":1625654313000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01305237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,12]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,12]]}},"alternative-id":["BF01305237"],"URL":"https:\/\/doi.org\/10.1007\/bf01305237","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,12]]}}}