{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,2]],"date-time":"2025-09-02T10:43:09Z","timestamp":1756809789444},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,5,19]],"date-time":"2011-05-19T00:00:00Z","timestamp":1305763200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s00224-011-9334-7","type":"journal-article","created":{"date-parts":[[2011,5,18]],"date-time":"2011-05-18T05:42:46Z","timestamp":1305697366000},"page":"282-296","source":"Crossref","is-referenced-by-count":2,"title":["Avoiding Simplicity is Complex"],"prefix":"10.1007","volume":"51","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Holger","family":"Spakowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,19]]},"reference":[{"key":"9334_CR1","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 39, 101\u2013124 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9334_CR2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1007\/978-3-642-77735-6_2","volume-title":"Kolmogorov Complexity and Computational Complexity","author":"E. Allender","year":"1992","unstructured":"Allender, E.: Applications of time-bounded Kolmogorov complexity in complexity theory. In: Watanabe, O. (ed.) Kolmogorov Complexity and Computational Complexity, pp. 4\u201322. Springer, Berlin (1992)"},{"key":"9334_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-45294-X_1","volume-title":"Proc. Conf. on Found. of Software Technology and Theo. Comp. Sci. (FST&TCS)","author":"E. Allender","year":"2001","unstructured":"Allender, E.: When worlds collide: derandomization, lower bounds, and Kolmogorov complexity. In: Proc. Conf. on Found. of Software Technology and Theo. Comp. Sci. (FST&TCS). Lecture Notes in Computer Science, vol. 2245, pp. 1\u201315 (2001)"},{"key":"9334_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-13962-8_1","volume-title":"Programs, Proofs, Processes, Proc. 6th Conference of Computability in Europe (CiE 2010)","author":"E. Allender","year":"2010","unstructured":"Allender, E.: Avoiding simplicity is complex. In: Programs, Proofs, Processes, Proc. 6th Conference of Computability in Europe (CiE 2010). Lecture Notes in Computer Science, vol. 6158, pp. 1\u201310 (2010)"},{"key":"9334_CR5","doi-asserted-by":"crossref","first-page":"1467","DOI":"10.1137\/050628994","volume":"35","author":"E. Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35, 1467\u20131493 (2006)","journal-title":"SIAM J. Comput."},{"key":"9334_CR6","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.jcss.2010.06.004","volume":"77","author":"E. Allender","year":"2011","unstructured":"Allender, E., Kouck\u00fd, M., Ronneburger, D., Roy, S.: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77, 14\u201340 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9334_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity, a\u00a0Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity, a\u00a0Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"9334_CR8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3\u201340 (1991)","journal-title":"Comput. Complex."},{"key":"9334_CR9","doi-asserted-by":"crossref","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. Comput. Complex. 3, 307\u2013318 (1993)","journal-title":"Comput. Complex."},{"issue":"3","key":"9334_CR10","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1137\/S009753979834388X","volume":"31","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., Fortnow, L., Laplante, S.: Resource-bounded Kolmogorov complexity revisited. SIAM J. Comput. 31(3), 887\u2013905 (2002)","journal-title":"SIAM J. Comput."},{"key":"9334_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-642-02927-1_18","volume-title":"Proc. of International Conference on Automata, Languages, and Programming (ICALP)","author":"H. Buhrman","year":"2009","unstructured":"Buhrman, H., Fortnow, L., Santhanam, R.: Unconditional lower bounds against advice. In: Proc. of International Conference on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 5555, pp. 195\u2013209 (2009)"},{"key":"9334_CR12","author":"B. Fu","year":"2011","unstructured":"Fu, B., Li, A., Zhang, L.: Separating NE from some nonuniform nondeterministic complexity classes. J. Comb. Optim. (2011). doi: 10.1007\/s10878-010-9327-5 . To appear; an earlier version appeared in COCOON 2009","journal-title":"J. Comb. Optim."},{"key":"9334_CR13","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1007\/BF01276437","volume":"2","author":"J. Goldsmith","year":"1992","unstructured":"Goldsmith, J., Hemachandra, L.A., Kunen, K.: Polynomial-time compression. Comput. Complex. 2, 18\u201339 (1992)","journal-title":"Comput. Complex."},{"issue":"2\/3","key":"9334_CR14","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"Hartmanis, J., Immerman, N., Sewelson, V.: Sparse sets in NP-P: EXPTIME versus NEXPTIME. Inf. Control 65(2\/3), 158\u2013181 (1985)","journal-title":"Inf. Control"},{"key":"9334_CR15","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L., Luby, M.: A\u00a0pseudorandom generator from any one-way function. SIAM J. Comput. 28, 1364\u20131396 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9334_CR16","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R. Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: exponential time vs. probabilistic polynomial time. J.\u00a0Comput. Syst. Sci. 65(4), 672\u2013694 (2002)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9334_CR17","first-page":"222","volume-title":"Proc. IEEE Symp. on Found. of Comp. Sci. (FOCS)","author":"R. Impagliazzo","year":"1989","unstructured":"Impagliazzo, R., Tardos, G.: Decision versus search problems in super-polynomial time. In: Proc. IEEE Symp. on Found. of Comp. Sci. (FOCS), pp. 222\u2013227 (1989)"},{"key":"9334_CR18","first-page":"220","volume-title":"Proc. ACM Symp. on Theory of Computing (STOC) \u201997","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: derandomizing the XOR lemma. In: Proc. ACM Symp. on Theory of Computing (STOC) \u201997, pp. 220\u2013229 (1997)"},{"key":"9334_CR19","doi-asserted-by":"crossref","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. Inf. Control 61, 15\u201337 (1984)","journal-title":"Inf. Control"},{"key":"9334_CR20","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39, 859\u2013868 (1992)","journal-title":"J. ACM"},{"key":"9334_CR21","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"Seiferas, J., Fischer, M., Meyer, A.: Separating nondeterministic time complexity classes. J. ACM 25, 146\u2013167 (1978)","journal-title":"J. ACM"},{"key":"9334_CR22","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A. Shamir","year":"1992","unstructured":"Shamir, A.: IP=PSPACE. J. ACM 39, 869\u2013877 (1992)","journal-title":"J. ACM"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9334-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9334-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9334-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:23Z","timestamp":1558698863000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9334-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,19]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9334"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9334-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,19]]}}}