{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T15:54:57Z","timestamp":1783007697687,"version":"3.54.5"},"reference-count":30,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2002,12,1]],"date-time":"2002-12-01T00:00:00Z","timestamp":1038700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3917,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2002,12]]},"DOI":"10.1016\/s0022-0000(02)00024-7","type":"journal-article","created":{"date-parts":[[2002,12,27]],"date-time":"2002-12-27T13:04:53Z","timestamp":1040994293000},"page":"672-694","source":"Crossref","is-referenced-by-count":120,"title":["In search of an easy witness: exponential time vs. probabilistic polynomial time"],"prefix":"10.1016","volume":"65","author":[{"given":"Russell","family":"Impagliazzo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valentine","family":"Kabanets","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/S0022-0000(02)00024-7_BIBACR98","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/273865.273933","article-title":"A new general derandomization method","volume":"45","author":"Andreev","year":"1998","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBAB85","doi-asserted-by":"crossref","unstructured":"L. Babai, Trading group theory for randomness, in: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 421\u2013429.","DOI":"10.1145\/22145.22192"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBFL91","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","article-title":"Non-deterministic exponential time has two-prover interactive protocols","volume":"1","author":"Babai","year":"1991","journal-title":"Comput. Complexity"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBFNW93","first-page":"307","article-title":"BPP has subexponential time simulations unless EXPTIME has publishable proofs","volume":"3","author":"Babai","year":"1993","journal-title":"Complexity"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBM88","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","article-title":"Arthur\u2013Merlin games","volume":"36","author":"Babai","year":"1988","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBAR01","doi-asserted-by":"crossref","unstructured":"B. Barak, How to go beyond the black-box simulation barrier, in: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 106\u2013115.","DOI":"10.1109\/SFCS.2001.959885"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBGI01","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, K. Yang, On the (im)possibility of obfuscating programs, in: J. Kilian (Ed.), Advances in Cryptology\u2014CRYPTO\u20192001, Lecture Notes in Computer Science, Vol. 2139, Springer, Berlin, Germany, 2001, pp. 1\u201318.","DOI":"10.1007\/3-540-44647-8_1"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBFT98","unstructured":"H. Buhrman, L. Fortnow, L. Thierauf, Nonrelativizing separations, in: Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1988, pp. 8\u201312."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBBH92","doi-asserted-by":"crossref","unstructured":"H. Buhrman, S. Homer, Superpolynomial circuits, almost sparse oracles and the exponential hierarchy, in: R. Shyamasundar (Ed.), Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 652, Springer, Berlin, Germany, 1992, pp. 116\u2013127.","DOI":"10.1007\/3-540-56287-7_99"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBFOR01","unstructured":"L. Fortnow, Comparing notions of full derandomization, in: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001, pp. 28\u201334."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBGOL99","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Algorithms and Combinatorics Series, Vol. 17, Springer, Berlin, 1999.","DOI":"10.1007\/978-3-662-12521-2"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBGZ97","unstructured":"O. Goldreich, D. Zuckerman, Another proof that BPP\u2282 PH (and more), Electronic Colloquium on Computational Complexity, TR97-045, 1997."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBHIS85","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/S0019-9958(85)80004-8","article-title":"Sparse sets in NP\u2013P: EXPTIME versus NEXPTIME","volume":"65","author":"Hartmanis","year":"1985","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBIN88","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, M. Naor, Decision trees and downward closures, in: Proceedings of the 3rd Annual IEEE Conference on Structure in Complexity Theory, 1988, pp. 29\u201338.","DOI":"10.1109\/SCT.1988.5260"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBIT89","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, G. Tardos, Decision versus search problems in super-polynomial time, in: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 222\u2013227.","DOI":"10.1109\/SFCS.1989.63482"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBIW97","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, A. Wigderson. P=BPP if E requires exponential circuits: derandomizing the XOR Lemma, in: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBIW98","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, A. Wigderson, Randomness vs time: de-randomization under a uniform assumption, in: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 734\u2013743.","DOI":"10.1109\/SFCS.1998.743524"},{"issue":"2","key":"10.1016\/S0022-0000(02)00024-7_BIBKAB01","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2001.1763","article-title":"Easiness assumptions and hardness tests: trading time for zero error","volume":"63","author":"Kabanets","year":"2001","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBKAB02","first-page":"88","article-title":"Derandomization","volume":"76","author":"Kabanets","year":"2002","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBKRC00","unstructured":"V. Kabanets, C. Rackoff, S. Cook, Efficiently approximable real-valued functions, Electronic Colloquium on Computational Complexity, TR00-034, 2000."},{"issue":"3\u20134","key":"10.1016\/S0022-0000(02)00024-7_BIBKL82","first-page":"191","article-title":"Turing machines that take advice","volume":"28","author":"Karp","year":"1982","journal-title":"L'Enseignement Math."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBKM99","doi-asserted-by":"crossref","unstructured":"A. Klivans, D. van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 659\u2013667.","DOI":"10.1145\/301250.301428"},{"issue":"3","key":"10.1016\/S0022-0000(02)00024-7_BIBLU01","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s00037-001-8196-9","article-title":"Derandomizing Arthur\u2013Merlin games under uniform assumptions","volume":"10","author":"Lu","year":"2001","journal-title":"Comput. Complexity"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBMIL01","doi-asserted-by":"crossref","unstructured":"P.B. Miltersen, Drandomizing complexity classes, in: S. Rajasekaran, P. Pardalos, J. Reif, J. Rolim (Eds.), Handbook of Randomized Computing, Vol. II, Kluwer Academic Publishers, Dordrecht, 2001 (a draft is available at www.brics.dk\/~bromille).","DOI":"10.1007\/978-1-4615-0013-1_19"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBMV99","doi-asserted-by":"crossref","unstructured":"P.B. Miltersen, N.V. Vinodchandran, Derandomizing Arthur\u2013Merlin games using hitting sets, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 71\u201380.","DOI":"10.1109\/SFFCS.1999.814579"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBNW94","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","article-title":"Hardness vs. randomness","volume":"49","author":"Nisan","year":"1994","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBPAP94","series-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBRR97","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jcss.1997.1494","article-title":"Natural proofs","volume":"55","author":"Razborov","year":"1997","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(02)00024-7_BIBSTV99","doi-asserted-by":"crossref","unstructured":"M. Sudan, L. Trevisan, S. Vadhan, Pseudorandom generators without the XOR lemma, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 537\u2013546.","DOI":"10.1109\/CCC.1999.766253"},{"key":"10.1016\/S0022-0000(02)00024-7_BIBYAO82","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Theory and applications of trapdoor functions, in: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, 1982, pp. 80\u201391.","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000247?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000002000247?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T10:29:34Z","timestamp":1554028174000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000002000247"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["S0022000002000247"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(02)00024-7","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}