{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T11:47:16Z","timestamp":1768909636500,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,9,20]],"date-time":"2011-09-20T00:00:00Z","timestamp":1316476800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s00037-011-0019-z","type":"journal-article","created":{"date-parts":[[2011,9,19]],"date-time":"2011-09-19T03:42:53Z","timestamp":1316403773000},"page":"3-61","source":"Crossref","is-referenced-by-count":16,"title":["Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds"],"prefix":"10.1007","volume":"21","author":[{"given":"Jeff","family":"Kinne","sequence":"first","affiliation":[]},{"given":"Dieter","family":"van Melkebeek","sequence":"additional","affiliation":[]},{"given":"Ronen","family":"Shaltiel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,20]]},"reference":[{"key":"19_CR1","unstructured":"Scott Aaronson Dieter van Melkebeek (2010). A note on circuit lower bounds from derandomization. Electronic Colloquium on Computational Complexity (ECCC), 17(105)."},{"issue":"1","key":"19_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1490270.1490272","volume":"1","author":"Scott Aaronson","year":"2009","unstructured":"Aaronson Scott, Wigderson Avi (2009) Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory, 1(1): 1\u201354","journal-title":"ACM Transactions on Computation Theory,"},{"key":"19_CR3","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Leonid A. Levin & Mario Szegedy (1991). Checking computations in polylogarithmic time. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 21\u201331."},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Lance Fortnow, Noam Nisan & Avi Wigderson (1993). BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3, 307\u2013318.","DOI":"10.1007\/BF01275486"},{"key":"19_CR5","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L\u00e1szl\u00f3 Babai","year":"1993","unstructured":"Babai L\u00e1szl\u00f3, Fortnow Lance, Nisan Noam, Wigderson Avi (1993) BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3: 307\u2013318","journal-title":"Computational Complexity"},{"key":"19_CR6","unstructured":"Aviad Cohen & Avi Wigderson (1989). Dispersers, deterministic amplification, & weak random sources (extended abstract). In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 14\u201319."},{"key":"19_CR7","unstructured":"Oded Goldreich, Noam Nisan & Avi Wigderson (1995). On Yao\u2019s XOR-lemma. Electronic Colloquium on Computational Complexity (ECCC), 2(50)."},{"key":"19_CR8","unstructured":"Oded Goldreich & Avi Wigderson (2000). On pseudorandomness with respect to deterministic observers. In Carleton Scientific, editor, International Colloquium on Automata, Languages and Programming (ICALP), pages 77\u201384."},{"key":"19_CR9","unstructured":"Oded Goldreich & Avi Wigderson (2002). Derandomization that is rarely wrong from short advice that is typically good. In Proceedings of the International Workshop on Randomization and Computation (RANDOM), pages 209\u2013223."},{"issue":"3-4","key":"19_CR10","first-page":"85","volume":"12","author":"Dan Gutfreund","year":"2003","unstructured":"Gutfreund Dan, Shaltiel Ronen, Ta-Shma Amnon (2003) Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Computational Complexity 12(3-4): 85\u2013130","journal-title":"Computational Complexity"},{"key":"19_CR11","volume-title":"Computational limitations of small-depth circuits","author":"Johan H\u00e5stad","year":"1987","unstructured":"H\u00e5stad Johan (1987) Computational limitations of small-depth circuits. MIT Press, Cambridge, MA, USA."},{"issue":"4","key":"19_CR12","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"Russell Impagliazzo","year":"2002","unstructured":"Impagliazzo Russell, Kabanets Valentine, Wigderson Avi (2002) In search of an easy witness: exponential time vs probabilistic polynomial time. Journal of Computer and System Sciences 65(4): 672\u2013694","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (1995). Hard-core distributions for somewhat hard problems. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 538\u2013545.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"19_CR14","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 220\u2013229."},{"issue":"4","key":"19_CR15","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1006\/jcss.2001.1780","volume":"63","author":"Russell Impagliazzo","year":"2001","unstructured":"Impagliazzo Russell, Wigderson Avi (2001) Randomness vs time: Derandomization under a uniform assumption. Journal of Computer and System Sciences 63(4): 672\u2013688","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR16","unstructured":"Russell Impagliazzo & David Zuckerman (1989). How to recycle random bits. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 248\u2013253."},{"issue":"2","key":"19_CR17","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2001.1763","volume":"63","author":"Valentine Kabanets","year":"2001","unstructured":"Kabanets Valentine (2001) Easiness assumptions and hardness tests: Trading time for zero error. Journal of Computer and System Sciences 63(2): 236\u2013252","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\/2","key":"19_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"Valentine Kabanets","year":"2004","unstructured":"Kabanets Valentine, Impagliazzo Russell (2004) Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1\/2): 1\u201346","journal-title":"Computational Complexity"},{"issue":"1","key":"19_CR19","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"Ravi Kannan","year":"1982","unstructured":"Kannan Ravi (1982) Circuit-size lower bounds and nonreducibility to sparse sets. Information and Control 55(1): 40\u201356","journal-title":"Information and Control"},{"issue":"5","key":"19_CR20","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"R. Klivans Adam","year":"2002","unstructured":"Klivans Adam R., van Melkebeek Dieter (2002) Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing 31(5): 1501\u20131526","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"19_CR21","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1137\/S0097539703438629","volume":"35","author":"Dieter Melkebeek van","year":"2005","unstructured":"van Melkebeek Dieter, Santhanam Rahul (2005) Holographic proofs and derandmization. SIAM Journal on Computing 35(1): 59\u201390","journal-title":"SIAM Journal on Computing"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Peter Bro Miltersen (2001). Derandomizing complexity classes. In Handbook of Randomized Computing, pages 843\u2013941. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-0013-1_19"},{"issue":"3","key":"19_CR23","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/s00037-005-0197-7","volume":"14","author":"Bro Miltersen Peter","year":"2005","unstructured":"Miltersen Peter Bro, Vinodchandran N. V. (2005) Derandomizing Arthur-Merlin games using hitting sets. Computational Complexity 14(3): 256\u2013279","journal-title":"Computational Complexity"},{"issue":"2","key":"19_CR24","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"Ilan Newman","year":"1991","unstructured":"Newman Ilan (1991) Private vs common random bits in communication complexity. Information Processing Letters 39(2): 67\u201371","journal-title":"Information Processing Letters"},{"issue":"1","key":"19_CR25","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01375474","volume":"11","author":"Noam Nisan","year":"1991","unstructured":"Nisan Noam (1991) Pseudorandom bits for constant depth circuits. Combinatorica 11(1): 63\u201370","journal-title":"Combinatorica"},{"issue":"1","key":"19_CR26","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(93)90258-U","volume":"107","author":"Noam Nisan","year":"1993","unstructured":"Nisan Noam (1993) On read-once vs multiple access to randomness in logspace. Theoretical Computer Science 107(1): 135\u2013144","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"19_CR27","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Noam Nisan","year":"1994","unstructured":"Nisan Noam, Wigderson Avi (1994) Hardness vs randomness. Journal of Computer and System Sciences 49(2): 149\u2013167","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Omer Reingold (2008). Undirected connectivity in log-space. Journal of the ACM, 55(4).","DOI":"10.1145\/1391289.1391291"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Ronen Shaltiel (2009). Weak derandomization of weak algorithms: explicit versions of Yao\u2019s lemma. In Proceedings of the IEEE Conference on Computational Complexity.","DOI":"10.1109\/CCC.2009.27"},{"issue":"2","key":"19_CR30","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/1059513.1059516","volume":"52","author":"Ronen Shaltiel","year":"2005","unstructured":"Shaltiel Ronen, Umans Christopher (2005) Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM 52(2): 172\u2013216","journal-title":"Journal of the ACM"},{"issue":"4","key":"19_CR31","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/s00037-007-0218-9","volume":"15","author":"Ronen Shaltiel","year":"2006","unstructured":"Shaltiel Ronen, Umans Christopher (2006) Pseudorandomness for approximate counting and sampling. Computational Complexity 15(4): 298\u2013341","journal-title":"Computational Complexity"},{"key":"19_CR32","unstructured":"Ronen Shaltiel & Christopher Umans (2007). Low-end uniform hardness vs. randomness tradeoffs for AM. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 430\u2013439."},{"issue":"4","key":"19_CR33","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"Adi Shamir","year":"1992","unstructured":"Shamir Adi (1992) IP = PSPACE. Journal of the ACM 39(4): 869\u2013877","journal-title":"Journal of the ACM"},{"issue":"2","key":"19_CR34","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1006\/jcss.1998.1616","volume":"58","author":"E. Saks Michael","year":"1999","unstructured":"Saks Michael E., Zhou Shiyu (1999) BPHSPACE(S) $${\\subseteq}$$ DSPACE(S3\/2). Journal of Computer and System Sciences 58(2): 376\u2013403","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"19_CR35","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"Seinosuke Toda","year":"1991","unstructured":"Toda Seinosuke (1991) PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing 20(5): 865\u2013877","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"19_CR36","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"Luca Trevisan","year":"2007","unstructured":"Trevisan Luca, Vadhan Salil P. (2007) Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity 16(4): 331\u2013364","journal-title":"Computational Complexity"},{"issue":"3-4","key":"19_CR37","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"Emanuele Viola","year":"2005","unstructured":"Viola Emanuele (2005) The complexity of constructing pseudorandom generators from hard functions. Computational Complexity 13(3-4): 147\u2013188","journal-title":"Computational Complexity"},{"issue":"5","key":"19_CR38","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1137\/050640941","volume":"36","author":"Emanuele Viola","year":"2006","unstructured":"Viola Emanuele (2006) Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM Journal on Computing 36(5): 1387\u20131403","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"19_CR39","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"B. Wilson Christopher","year":"1985","unstructured":"Wilson Christopher B. (1985) Relativized circuit complexity. Journal of Computer and System Sciences 31(2): 169\u2013181","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"19_CR40","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1142\/S0129054191000066","volume":"2","author":"Viktoria Zanko","year":"1991","unstructured":"Zanko Viktoria (1991) #P-completeness via many-one reductions. International Journal of Foundations of Computer Science 2(1): 77\u201382","journal-title":"International Journal of Foundations of Computer Science"},{"key":"19_CR41","doi-asserted-by":"crossref","unstructured":"Marius Zimand (2006). Exposure-resilient extractors. In Proceedings of the IEEE Conference on Computational Complexity, pages 61\u201372.","DOI":"10.1109\/CCC.2006.19"},{"issue":"2","key":"19_CR42","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/s00037-008-0243-3","volume":"17","author":"Marius Zimand","year":"2008","unstructured":"Zimand Marius (2008) Exposure-resilient extractors and the derandomization of probabilistic sublinear time. Computational Complexity, 17(2): 220\u2013253","journal-title":"Computational Complexity,"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0019-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0019-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0019-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,15]],"date-time":"2019-06-15T19:26:32Z","timestamp":1560626792000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0019-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,20]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["19"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0019-z","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,20]]}}}