{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:04:23Z","timestamp":1775282663751,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1991,3,1]],"date-time":"1991-03-01T00:00:00Z","timestamp":667785600000},"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":[[1991,3]]},"DOI":"10.1007\/bf01375474","type":"journal-article","created":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T20:19:45Z","timestamp":1112386785000},"page":"63-70","source":"Crossref","is-referenced-by-count":121,"title":["Pseudorandom bits for constant depth circuits"],"prefix":"10.1007","volume":"11","author":[{"given":"Noam","family":"Nisan","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"L. Adleman: Two theorems on random polynomial time,19th FOCS pp. 75?83, 1978.","DOI":"10.1109\/SFCS.1978.37"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai: ? 1 1 formulas on finite structures.Annals of Pure and Applied Logic 24, pp. 1?48. 1983.","journal-title":"Annals of Pure and Applied Logic"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai, andM. Ben-Or: A theorem on probabilistic constant depth computations,16th STOC, pp. 571?474, 1984.","DOI":"10.1145\/800057.808715"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"M. Ajtai, andA. Wigderson: Deterministic simulation of probabilistic constant depth circuits26th FOCS, pp. 11?19, 1985.","DOI":"10.1109\/SFCS.1985.19"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"L. Babai: Trading group theory for randomness17th STOC, pp. 421?429, 1975.","DOI":"10.1145\/22145.22192"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"C. H. Benett, andJ. Gill: Relative to a random oracleA, P A ?NP A ?Co-NP A with probability 1.SIAM J. Comp. 10, 1981.","DOI":"10.1137\/0210008"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai, andS. Moran: Arthur Merlin games: a randomized proof system, and a hierarchy of complexity classes,J. Computer Sys. Sci. 36, pp. 254?276, 1988.","journal-title":"J. Computer Sys. Sci."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"M. Blum, andS. Micali: How to generate cryptographically strong sequences of pseudo random bits.23rd FOCS, pp. 112?117, 1982.","DOI":"10.1109\/SFCS.1982.72"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"A. Chandra, D. Kozen, andL. Stockmeyer: Alternation,J. ACM,28, 1981.","DOI":"10.1145\/322234.322243"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"M. Furst, R. J. Lipton, andL. Stoclmeyer: Pseudo random number generation and space complexity,Information and Control,64, 1985.","DOI":"10.1016\/S0019-9958(85)80043-7"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Saxe, andM. Sipser: Parity, Circuits, and the polynomial time hierarchy,22nd FOCS, pp. 260?270, 1981.","DOI":"10.1109\/SFCS.1981.35"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, andS. Micali: Probabilistic Encryption,JCSS,28, No. 2, 1984.","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, andM. Sipser: Private coins vs. Public voins in interactive proof systems,18th STOC, pp. 59?68, 1986.","DOI":"10.1145\/12130.12137"},{"key":"CR14","unstructured":"J. Hastad:Lower Bounds for the Size of Parity Circuits, Ph.D. Thesis, M.I.T., 1987."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"S. A. Kurts: A note on randomized polynomial time,SIAM J. Comp. 16, No. 5, 1987.","DOI":"10.1137\/0216056"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"N. Nisan, andA. Wigderson: Hardness vs. Randomness,29th FOCS, 1988.","DOI":"10.1109\/SFCS.1988.21916"},{"key":"CR17","unstructured":"J. H. Reif, andJ. D. Tygar: Towards a theory of parallel randomized computation,TR-07-84, Aiken Computation Lab., Harvard University, 1984."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"M. Sipser: A complexity theoretic approach to randomness,15th STOC, 330?335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"M. Sipser: Expanders, Randomness, or Time vs. Space, Structure in Complexity Theory, Lecture notes in Computer Science, No. 223, Ed. G. Goos, J. Hartmanis, pp. 325?329.","DOI":"10.1007\/3-540-16486-3_108"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer: The polynomial time hierarchy,Theory. Comp. Sci. 3, No. 1, 1976.","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"A. C. Yao: Theory and applications of trapdoor functions,23rd FOCS, pp. 80?91, 1982.","DOI":"10.1109\/SFCS.1982.45"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"A. C. Yao: Separating the polynomial time hierarchy by oracles,26th FOCS, pp. 1?10, 1985.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01375474.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01375474\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01375474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,29]],"date-time":"2024-12-29T23:22:57Z","timestamp":1735514577000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01375474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["BF01375474"],"URL":"https:\/\/doi.org\/10.1007\/bf01375474","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}