{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,27]],"date-time":"2026-04-27T11:01:59Z","timestamp":1777287719670,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540430025","type":"print"},{"value":"9783540452942","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_1","type":"book-chapter","created":{"date-parts":[[2007,6,11]],"date-time":"2007-06-11T22:45:12Z","timestamp":1181601912000},"page":"1-15","source":"Crossref","is-referenced-by-count":17,"title":["When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences 36 (1988) 254\u2013276","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complement. SIAM Journal on Computing 17 (1988) 935\u2013938","journal-title":"SIAM Journal on Computing"},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Informatica 26 (1988) 279\u2013284","journal-title":"Acta Informatica"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karlo., H., Nisan, N.: Algebraic methods for interactive proof systems. Journal of the ACM 39 (1992) 859\u2013868","journal-title":"Journal of the ACM"},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. Journal of the ACM 39 (1992) 869\u2013877","journal-title":"Journal of the ACM"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences 55 (1997) 24\u201335","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR7","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, New York (1994)"},{"key":"1_CR8","volume-title":"Theory of Computational Complexity","author":"D.Z. Du","year":"2000","unstructured":"Du, D.Z., Ko, K.I.: Theory of Computational Complexity. Wiley-Interscience, New York (2000)"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity. Springer-Verlag (1999)","DOI":"10.1007\/978-3-662-03927-4"},{"key":"1_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0304-3975(84)90111-7","volume":"34","author":"J. Hartmanis","year":"1984","unstructured":"Hartmanis, J., Yesha, Y.: Computation times of NP sets of different densities. Theoretical Computer Science 34 (1984) 17\u201332","journal-title":"Theoretical Computer Science"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1137\/0217075","volume":"17","author":"E. Allender","year":"1988","unstructured":"Allender, E., Rubinstein, R.: P-printable sets. SIAM J. Comput. 17 (1988) 1193\u20131202","journal-title":"SIAM J. Comput"},{"key":"1_CR12","volume-title":"Computational Limitations of Small Depth Circuits","author":"J. H\u00f8astad","year":"1988","unstructured":"H\u00f8astad, J.: Computational Limitations of Small Depth Circuits. MIT Press, Cambridge (1988)"},{"key":"1_CR13","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0890-5401(90)90052-J","volume":"86","author":"E. Allender","year":"1990","unstructured":"Allender, E., Watanabe, O.: Kolmogorov complexity and degrees of tally sets. Information and Computation 86 (1990) 160\u2013178","journal-title":"Information and Computation"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Tardos, G.: Decision versus search problems in super-polynomial time. In: IEEE Symposium on Foundations of Computer Science (FOCS). (1989) 222\u2013227","DOI":"10.1109\/SFCS.1989.63482"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L., Laplante, S.: Resource-bounded Kolmogorov complexity revisited. SIAM Journal on Computing (2001) to appear; a preliminary version appeared in STACS 1997.","DOI":"10.1007\/BFb0023452"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-1","volume":"61","author":"L.A. Levin","year":"1984","unstructured":"Levin, L.A.: Randomness conservation inequalities; information and independence in mathematical theories. Information and Control 61 (1984) 15\u201337","journal-title":"Information and Control"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0022-0000(89)90021-4","volume":"39","author":"E. Allender","year":"1989","unstructured":"Allender, E.: Some consequences of the existence of pseudorandom generators. Journal of Computer and System Sciences 39 (1989) 101\u2013124","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Allender, E.: Applications of time-bounded kolmogorov complexity in complexity theory. In: Osamu Watanabe (Ed.), Kolmogorov Complexity and Computational Complexity. Springer-Verlag (1992) 4\u201322","DOI":"10.1007\/978-3-642-77735-6_2"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: ACM Symposium on Theory of Computing (STOC). (1997) 220\u2013229","DOI":"10.1145\/258533.258590"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences 62 (2001) 236\u2013266","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR21","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(99)00164-4","volume":"255","author":"V. Arvind","year":"2001","unstructured":"Arvind, V., K\u00f6bler, J.: On pseudorandomness and resource-bounded measure. Theoretical Computer Science 255 (2001) 205\u2013221","journal-title":"Theoretical Computer Science"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In: ACM Symposium on Theory of Computing (STOC). (1999) 659\u2013667","DOI":"10.1145\/301250.301428"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. In: IEEE Symposium on Foundations of Computer Science (FOCS). (1999) 71\u201380","DOI":"10.1109\/SFFCS.1999.814579"},{"key":"1_CR24","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3 (1993) 307\u2013318","journal-title":"Computational Complexity"},{"key":"1_CR25","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. In: IEEE Conference on Computational Complexity. (2001) 2\u201312"},{"key":"1_CR26","unstructured":"Antunes, L., Fortnow, L., van Melkebeek, D.: Computational depth. In: IEEE Conference on Computational Complexity. (2001) 266\u2013273"},{"key":"1_CR27","unstructured":"Ronneburger, D.: Personal communication. (2001)"},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness. Journal of Computer and System Sciences 49 (1994) 149\u2013167","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Near-optimal conversion of hardness into pseudo-randomness. In: IEEE Symposium on Foundations of Computer Science (FOCS). (1999) 181\u2013190","DOI":"10.1109\/SFFCS.1999.814590"},{"key":"1_CR30","unstructured":"Fortnow, L.: Comparing notions of full derandomization. In: IEEE Conference on Computational Complexity. (2001) 28\u201334"},{"key":"1_CR31","unstructured":"Kabanets, V., Racko., C., Cook, S.: Efficiently approximable real-valued functions. In: Electronic Colloquium on Computational Complexity (ECCC) Report TR00-034. (2000) ( http:\/\/www.eccc.uni-trier.de\/eccc )."},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00054-9","volume":"62","author":"M. Zimand","year":"1997","unstructured":"Zimand, M.: Large sets in AC0 have many strings with low Kolmogorov complexity. Information Processing Letters 62 (1997) 165\u2013170","journal-title":"Information Processing Letters"},{"key":"1_CR33","series-title":"Lect Notes Comput Sci","volume-title":"Hard sets and pseudo-random generators for constant depth circuits","author":"M. Agrawal","year":"2001","unstructured":"Agrawal, M.: Hard sets and pseudo-random generators for constant depth circuits. In: Proceedings 21st Foundations of Software Technology and Theoretical Computer Science Conference (FST&TCS). Lecture Notes in Computer Science, Springer (2001) (these proceedings)."},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Regan, K.W., Sivakumar, D., Cai, J.Y.: Pseudorandom generators, measure theory, and natural proofs. In: IEEE Symposium on Foundations of Computer Science (FOCS). (1995) 26\u201335","DOI":"10.1109\/SFCS.1995.492459"},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences 44 (1992) 220\u2013258","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1137\/S0097539799360148","volume":"30","author":"H. Buhrman","year":"2001","unstructured":"Buhrman, H., Torenvliet, L.: Randomness is hard. SIAM Journal on Computing 30 (2001) 1485\u20131501","journal-title":"SIAM Journal on Computing"},{"key":"1_CR37","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1137\/0220059","volume":"20","author":"K.I. Ko","year":"1991","unstructured":"Ko, K.I.: On the complexity of learning minimum time-bounded Turing machines. SIAM Journal on Computing 20 (1991) 962\u2013986","journal-title":"SIAM Journal on Computing"},{"key":"1_CR38","unstructured":"Hartmanis, J.: Generalized Kolmogorov complexity and the structure of feasible computations (preliminary report). In: IEEE Symposium on Foundations of Computer Science (FOCS). (1983) 439\u2013445"},{"key":"1_CR39","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Cai, J.Y.: Circuit minimization problem. In: ACM Symposium on Theory of Computing (STOC). (2000) 73\u201379","DOI":"10.1145\/335305.335314"},{"key":"1_CR40","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1006\/jcss.1997.1484","volume":"54","author":"H. Buhrman","year":"1997","unstructured":"Buhrman, H., Mayordomo, E.: An excursion to the Kolmogorov random strings. Journal of Computer and System Sciences 54 (1997) 393\u2013399","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR41","series-title":"Lect Notes Comput Sci","volume-title":"The first-order isomorphism theorem","author":"M. Agrawal","year":"2001","unstructured":"Agrawal, M.: The first-order isomorphism theorem. In: Proceedings 21st Foundations of Software Technology and Theoretical Computer Science Conference (FST&TCS). Lecture Notes in Computer Science, Springer (2001) (these proceedings)."},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Construction of extractors using pseudo-random generators. Journal of the ACM (2001) to appear; a preliminary version appeared in STOC 1999.","DOI":"10.1145\/301250.301289"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T21:27:53Z","timestamp":1556486873000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}