{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T14:52:03Z","timestamp":1784299923925,"version":"3.55.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,12,1]],"date-time":"1993-12-01T00:00:00Z","timestamp":754704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1993,12]]},"DOI":"10.1007\/bf01275486","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T08:08:55Z","timestamp":1111651735000},"page":"307-318","source":"Crossref","is-referenced-by-count":214,"title":["BPP has subexponential time simulations unlessEXPTIME has publishable proofs"],"prefix":"10.1007","volume":"3","author":[{"given":"L?szl\ufffd","family":"Babai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noam","family":"Nisan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"L. Adleman, Two theorems on random polynomial time, inProceedings of the 19th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1978, 75?83.","DOI":"10.1109\/SFCS.1978.37"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"L. Babai, Trading group theory for randomness, inProceedings of the 17th ACM Symposium on the Theory of Computing, ACM, New York, 1985, 421?429.","DOI":"10.1145\/22145.22192"},{"issue":"1","key":"CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01200057","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai andL. Fortnow, Arithmetization: A new method in structural complexity theory,Computational Complexity,1:1 (1991), 41?66.","journal-title":"Computational Complexity"},{"issue":"1","key":"CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, andC. Lund, Non-deterministic exponential time has two-prover interactive protocols,Computational Complexity,1:1 (1991), 3?40.","journal-title":"Computational Complexity"},{"issue":"2","key":"CR5","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,Journal of Computer and System Sciences,36:2 (1988), 254?276.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR6","first-page":"37","volume-title":"Proceedings of the 7th Symposium on Theoretical Aspects of Computer Science, volume 415 ofLecture Notes in Computer Science","author":"D. Beaver","year":"1990","unstructured":"D. Beaver andJ. Feigenbaum, Hiding instances in multioracle queries, inProceedings of the 7th Symposium on Theoretical Aspects of Computer Science, volume 415 ofLecture Notes in Computer Science, Springer, Berlin, 1990, 37?48."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson, Multiprover interactive proofs: How to remove intractability assumptions, inProceedings of the 20th ACM Symposium on the Theory of Computing, ACM, New York, 1988, 113?131.","DOI":"10.1145\/62212.62223"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. Bennet","year":"1981","unstructured":"C. Bennet andJ. Gill, Relative to a random oracle,P A ? NPA ? co-NPA with probability one,SIAM Journal on Computing,10 (1981), 96?113.","journal-title":"SIAM Journal on Computing"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan, Designing programs that check their work, inProceedings of the 21st ACM Symposium on the Theory of Computing, ACM, New York, 1989, 86?97.","DOI":"10.1145\/73007.73015"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"M. Blum, M. Luby, and R. Rubinfeld, Self-testing and self-correcting programs, with applications to numerical programs, inProceedings of the 22nd ACM Symposium on the Theory of Computing, ACM, New York, 1990, 73?83.","DOI":"10.1145\/100216.100225"},{"key":"CR11","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 Journal on Computing,13 (1984), 850?864.","journal-title":"SIAM Journal on Computing"},{"key":"CR12","first-page":"1","volume-title":"Randomness and Computation, volume 5 ofAdvances in Computing Research","author":"R. Boppana","year":"1989","unstructured":"R. Boppana andR. Hirschfeld, Pseudorandom generators and complexity classes, inRandomness and Computation, volume 5 ofAdvances in Computing Research, S. Micali, ed., JAI Press, Greenwich, 1989, 1?26."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"O. Goldreich, H. Krawczyk, and M. Luby, On the existence of pseudorandom generators, inProceedings of the 29th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1988, 12?24.","DOI":"10.1109\/SFCS.1988.21917"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. Levin, A hard-core predicate for all one-way functions, inProceedings of the 21st ACM Symposium on the Theory of Computing, ACM, New York, 1989, 25?32.","DOI":"10.1145\/73007.73010"},{"issue":"1","key":"CR15","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, andC. Rackoff, The knowledge complexity of interactive proof-systems,SIAM Journal on Computing,18:1 (1989), 186?208.","journal-title":"SIAM Journal on Computing"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"J. H\ufffdstad, Pseudo-random generators under uniform assumptions, inProceedings of the 22nd ACM Symposium on the Theory of Computing, ACM, New York, 1990, 395?404.","DOI":"10.1145\/100216.100270"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis, N. Immerman, andV. Sewelson, Sparse sets inNP-P: EXPTIME versusNEXPTIME, Information and Control,65 (1985), 158?181.","journal-title":"Information and Control"},{"key":"CR18","first-page":"231","volume":"71","author":"H. Heller","year":"1986","unstructured":"H. Heller, On relativized exponential and probabilistic complexity classes,Information and Computation,71 (1986), 231?243.","journal-title":"Information and Computation"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. Levin, and M. Luby, Pseudo-random number generation from one-way functions, inProceedings of the 21st ACM Symposium on the Theory of Computing, ACM, New York, 1989, 12?24.","DOI":"10.1145\/73007.73009"},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes, inProceedings of the 12th ACM Symposium on the Theory of Computing, ACM, New York, 1980, 302?309.","DOI":"10.1145\/800141.804678"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"L. Levin","year":"1987","unstructured":"L. Levin, One-way functions and pseudo-random generators,Combinatorica,7 (1987), 357?363.","journal-title":"Combinatorica"},{"key":"CR22","first-page":"191","volume-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"R. Lipton","year":"1991","unstructured":"R. Lipton, New directions in testing, inDistributed Computing and Cryptography, volume 2 ofDIMACS Series in Discrete Mathematics and Theoretical Computer Science, J. Feigenbaum and M. Merritt, eds., American Mathematical Society, Providence, 1991, 191?202."},{"issue":"4","key":"CR23","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"C. Lund, L. Fortnow, H. Karloff, andN. Nisan, Algebraic methods for interactive proof systems,Journal of the ACM,39:4 (1992), 859?868.","journal-title":"Journal of the ACM"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Wigderson, Hardness vs. randomness, inProceedings of the 29th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1988, 2?11.","DOI":"10.1109\/SFCS.1988.21916"},{"issue":"4","key":"CR25","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"A. Shamir, IP=PSPACE,Journal of the ACM,39:4 (1992), 869?877.","journal-title":"Journal of the ACM"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"A. Yao, Theory and applications of trapdoor functions, inProceedings of the 23rd IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1982, 80?91.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01275486.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01275486\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01275486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T13:02:50Z","timestamp":1586178170000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01275486"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["BF01275486"],"URL":"https:\/\/doi.org\/10.1007\/bf01275486","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}