{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T01:01:15Z","timestamp":1740099675440,"version":"3.37.3"},"publisher-location":"Cham","reference-count":62,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030416713"},{"type":"electronic","value":"9783030416720"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-41672-0_2","type":"book-chapter","created":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T07:03:04Z","timestamp":1582182184000},"page":"8-18","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0650-028X","authenticated-orcid":false,"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"key":"2_CR1","unstructured":"Adleman, L.M.: Time, space and randomness. Technical report, MIT\/LCS\/TM-131, MIT (1979)"},{"key":"2_CR2","doi-asserted-by":"publisher","unstructured":"Allender, E.: Some consequences of the existence of pseudorandom generators. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 151\u2013159 (1987). https:\/\/doi.org\/10.1145\/28395.28412 , see also [3]","DOI":"10.1145\/28395.28412"},{"issue":"1","key":"2_CR3","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. J. Comput. Syst. Sci. 39(1), 101\u2013124 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90021-4","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Allender, E.: The new complexity landscape around circuit minimization. In: Proceedings of the 14th International Conference on Language and Automata Theory and Applications (LATA) (2020, to appear)","DOI":"10.1007\/978-3-030-40608-0_1"},{"key":"2_CR5","doi-asserted-by":"publisher","unstructured":"Allender, E., Buhrman, H., Friedman, L., Loff, B.: Reductions to the set of random strings: the resource-bounded case. Logical Methods Comput. Sci. 10(3) (2014). https:\/\/doi.org\/10.2168\/LMCS-10(3:5)2014","DOI":"10.2168\/LMCS-10(3:5)2014"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1137\/050628994","volume":"35","author":"E Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Koucky, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM J. Comput. 35, 1467\u20131493 (2006). https:\/\/doi.org\/10.1137\/050628994","journal-title":"SIAM J. Comput."},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.ic.2017.04.004","volume":"256","author":"E Allender","year":"2017","unstructured":"Allender, E., Das, B.: Zero knowledge and circuit minimization. Inf. Comput. 256, 2\u20138 (2017). https:\/\/doi.org\/10.1016\/j.ic.2017.04.004 . Special issue for MFCS 2014","journal-title":"Inf. Comput."},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1137\/17M1157970","volume":"47","author":"E Allender","year":"2018","unstructured":"Allender, E., Grochow, J., van Melkebeek, D., Morgan, A., Moore, C.: Minimum circuit size, graph isomorphism and related problems. SIAM J. Comput. 47, 1339\u20131372 (2018). https:\/\/doi.org\/10.1137\/17M1157970","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2_CR9","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/3349616","volume":"11","author":"E Allender","year":"2019","unstructured":"Allender, E., Hirahara, S.: New insights on the (non)-hardness of circuit minimization and related problems. ACM Trans. Comput. Theory (ToCT) 11(4), 27:1\u201327:27 (2019). https:\/\/doi.org\/10.1145\/3349616","journal-title":"ACM Trans. Comput. Theory (ToCT)"},{"issue":"2","key":"2_CR10","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s00037-016-0124-0","volume":"26","author":"E Allender","year":"2017","unstructured":"Allender, E., Holden, D., Kabanets, V.: The minimum oracle circuit size problem. Comput. Complex. 26(2), 469\u2013496 (2017). https:\/\/doi.org\/10.1007\/s00037-016-0124-0","journal-title":"Comput. Complex."},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-030-19955-5_2","volume-title":"Computer Science \u2013 Theory and Applications","author":"E Allender","year":"2019","unstructured":"Allender, E., Ilango, R., Vafa, N.: The non-hardness of approximating circuit size. In: van Bevern, R., Kucherov, G. (eds.) CSR 2019. LNCS, vol. 11532, pp. 13\u201324. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-19955-5_2"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.jcss.2010.06.004","volume":"77","author":"E Allender","year":"2010","unstructured":"Allender, E., Koucky, M., Ronneburger, D., Roy, S.: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci. 77, 14\u201340 (2010). https:\/\/doi.org\/10.1016\/j.jcss.2010.06.004","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR13","doi-asserted-by":"publisher","unstructured":"Allender, E., Watanabe, O.: Kolmogorov complexity and degrees of tally sets. In: Proceedings: Third Annual Structure in Complexity Theory Conference, pp. 102\u2013111. IEEE Computer Society (1988). https:\/\/doi.org\/10.1109\/SCT.1988.5269 , see also [14]","DOI":"10.1109\/SCT.1988.5269"},{"issue":"2","key":"2_CR14","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. Inf. Comput. 86(2), 160\u2013178 (1990). https:\/\/doi.org\/10.1016\/0890-5401(90)90052-J","journal-title":"Inf. Comput."},{"issue":"3","key":"2_CR15","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/j.tcs.2005.11.033","volume":"354","author":"L Antunes","year":"2006","unstructured":"Antunes, L., Fortnow, L., van Melkebeek, D., Vinodchandran, N.V.: Computational depth: concept and applications. Theor. Comput. Sci. 354(3), 391\u2013404 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.11.033","journal-title":"Theor. Comput. Sci."},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-55719-9_72","volume-title":"Automata, Languages and Programming","author":"V Arvind","year":"1992","unstructured":"Arvind, V., et al.: Reductions to sets of low information content. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 162\u2013173. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/3-540-55719-9_72 . See also [17]"},{"key":"2_CR17","unstructured":"Arvind, V., et al.: Reductions to sets of low information content. In: Ambos-Spies, K., Homer, S., Schoning, U. (eds.) Complexity Theory: Current Research, pp. 1\u201346. Cambridge University Press (1993)"},{"key":"2_CR18","doi-asserted-by":"publisher","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo random bits. In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 112\u2013117 (1982). https:\/\/doi.org\/10.1109\/SFCS.1982.72 , see also [19]","DOI":"10.1109\/SFCS.1982.72"},{"issue":"4","key":"2_CR19","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13(4), 850\u2013864 (1984). https:\/\/doi.org\/10.1137\/0213053","journal-title":"SIAM J. Comput."},{"key":"2_CR20","doi-asserted-by":"publisher","unstructured":"Book, R.V., Lutz, J.H.: On languages with very high information content. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pp. 255\u2013259. IEEE Computer Society (1992). https:\/\/doi.org\/10.1109\/SCT.1992.215400 , see also [21]","DOI":"10.1109\/SCT.1992.215400"},{"issue":"2","key":"2_CR21","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1137\/0222029","volume":"22","author":"RV Book","year":"1993","unstructured":"Book, R.V., Lutz, J.H.: On languages with very high space-bounded Kolmogorov complexity. SIAM J. Comput. 22(2), 395\u2013402 (1993). https:\/\/doi.org\/10.1137\/0222029","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2_CR22","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1137\/S009753979834388X","volume":"31","author":"H Buhrman","year":"2001","unstructured":"Buhrman, H., Fortnow, L., Laplante, S.: Resource-bounded Kolmogorov complexity revisited. SIAM J. Comput. 31(3), 887\u2013905 (2001). https:\/\/doi.org\/10.1137\/S009753979834388X","journal-title":"SIAM J. Comput."},{"key":"2_CR23","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. JCSS 54, 393\u2013399 (1997). https:\/\/doi.org\/10.1006\/jcss.1997.1484","journal-title":"JCSS"},{"issue":"3","key":"2_CR24","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0304-3975(77)90015-9","volume":"4","author":"R Daley","year":"1977","unstructured":"Daley, R.: On the inference of optimal descriptions. Theor. Comput. Sci. 4(3), 301\u2013319 (1977). https:\/\/doi.org\/10.1016\/0304-3975(77)90015-9","journal-title":"Theor. Comput. Sci."},{"key":"2_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3","volume-title":"Algorithmic Randomness and Complexity","author":"R Downey","year":"2010","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-0-387-68441-3"},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BFb0029618","volume-title":"Mathematical Foundations of Computer Science 1990","author":"R Gavald\u00e0","year":"1990","unstructured":"Gavald\u00e0, R., Torenvliet, L., Watanabe, O., Balc\u00e1zar, J.L.: Generalized Kolmogorov complexity in relativized separations (extended abstract). In: Rovan, B. (ed.) MFCS 1990. LNCS, vol. 452, pp. 269\u2013276. Springer, Heidelberg (1990). https:\/\/doi.org\/10.1007\/BFb0029618"},{"key":"2_CR27","doi-asserted-by":"publisher","unstructured":"Golovnev, A., Ilango, R., Impagliazzo, R., Kabanets, V., Kolokolova, A., Tal, A.: $${\\rm AC}^0[{\\rm p}]$$ lower bounds against MCSP via the coin problem. In: 46th International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 132, pp. 66:1\u201366:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.66","DOI":"10.4230\/LIPIcs.ICALP.2019.66"},{"key":"2_CR28","unstructured":"Hemachandra, L.A., Wechsung, G.: Using randomness to characterize the complexity of computation. In: Proceedings of the IFIP 11th World Computer Congress on Information Processing 1989, pp. 281\u2013286. North-Holland\/IFIP (1989), see also [29]"},{"issue":"2","key":"2_CR29","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0304-3975(91)90282-7","volume":"83","author":"LA Hemachandra","year":"1991","unstructured":"Hemachandra, L.A., Wechsung, G.: Kolmogorov characterizations of complexity classes. Theor. Comput. Sci. 83(2), 313\u2013322 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90282-7","journal-title":"Theor. Comput. Sci."},{"key":"2_CR30","doi-asserted-by":"publisher","unstructured":"Hirahara, S.: Non-black-box worst-case to average-case reductions within NP. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 247\u2013258 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00032","DOI":"10.1109\/FOCS.2018.00032"},{"key":"2_CR31","doi-asserted-by":"publisher","unstructured":"Hirahara, S., Santhanam, R.: On the average-case complexity of MCSP and its variants. In: 32nd Conference on Computational Complexity, CCC. LIPIcs, vol. 79, pp. 7:1\u20137:20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2017.7","DOI":"10.4230\/LIPIcs.CCC.2017.7"},{"key":"2_CR32","doi-asserted-by":"publisher","unstructured":"Hitchcock, J.M., Pavan, A.: On the NP-completeness of the minimum circuit size problem. In: Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). LIPIcs, vol. 45, pp. 236\u2013245. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2015.236","DOI":"10.4230\/LIPIcs.FSTTCS.2015.236"},{"key":"2_CR33","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)"},{"key":"2_CR34","doi-asserted-by":"publisher","unstructured":"Ilango, R.: Approaching MCSP from above and below: Hardness for a conditional variant and AC$$^0[p]$$. In: 11th Innovations in Theoretical Computer Science Conference, ITCS. LIPIcs, vol. 151, pp. 34:1\u201334:26. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.34","DOI":"10.4230\/LIPIcs.ITCS.2020.34"},{"key":"2_CR35","unstructured":"Ilango, R., Loff, B., Oliveira, I.C.: NP-hardness of minimizing circuits and communication (2019, manuscript)"},{"key":"2_CR36","doi-asserted-by":"publisher","unstructured":"Kabanets, V., Cai, J.Y.: Circuit minimization problem. In: ACM Symposium on Theory of Computing (STOC), pp. 73\u201379 (2000). https:\/\/doi.org\/10.1145\/335305.335314","DOI":"10.1145\/335305.335314"},{"issue":"3","key":"2_CR37","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0304-3975(86)90081-2","volume":"48","author":"K Ko","year":"1986","unstructured":"Ko, K.: On the notion of infinite pseudorandom sequences. Theor. Comput. Sci. 48(3), 9\u201333 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90081-2","journal-title":"Theor. Comput. Sci."},{"key":"2_CR38","doi-asserted-by":"crossref","unstructured":"Ko, K.: On the complexity of learning minimum time-bounded Turing machines. In: Proceedings of the Third Annual Workshop on Computational Learning Theory, (COLT), pp. 82\u201396 (1990), see also [39]","DOI":"10.1016\/B978-1-55860-146-8.50009-6"},{"issue":"5","key":"2_CR39","doi-asserted-by":"publisher","first-page":"962","DOI":"10.1137\/0220059","volume":"20","author":"K Ko","year":"1991","unstructured":"Ko, K.: On the complexity of learning minimum time-bounded Turing machines. SIAM J. Comput. 20(5), 962\u2013986 (1991). https:\/\/doi.org\/10.1137\/0220059","journal-title":"SIAM J. Comput."},{"key":"2_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/3-540-16486-3_99","volume-title":"Structure in Complexity Theory","author":"K-I Ko","year":"1986","unstructured":"Ko, K.-I., Orponen, P., Sch\u00f6ning, U., Watanabe, O.: What is a hard instance of a computational problem? In: Selman, A.L. (ed.) Structure in Complexity Theory. LNCS, vol. 223, pp. 197\u2013217. Springer, Heidelberg (1986). https:\/\/doi.org\/10.1007\/3-540-16486-3_99 . See also [51]"},{"issue":"1","key":"2_CR41","first-page":"1","volume":"1","author":"AN Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the quantitative definition ofinformation\u2019. Probl. Inf. Transm. 1(1), 1\u20137 (1965)","journal-title":"Probl. Inf. Transm."},{"key":"2_CR42","first-page":"265","volume":"9","author":"L Levin","year":"1973","unstructured":"Levin, L.: Universal search problems. Probl. Inf. Transm. 9, 265\u2013266 (1973)","journal-title":"Probl. Inf. Transm."},{"issue":"1","key":"2_CR43","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-l","volume":"61","author":"LA Levin","year":"1984","unstructured":"Levin, L.A.: Randomness conservation inequalities; information and independence in mathematical theories. Inf. Control 61(1), 15\u201337 (1984). https:\/\/doi.org\/10.1016\/S0019-9958(84)80060-l","journal-title":"Inf. Control"},{"key":"2_CR44","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11298-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"2019","unstructured":"Li, M., Vitanyi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science, 4th edn. Springer, Heidelberg (2019). https:\/\/doi.org\/10.1007\/978-3-030-11298-1","edition":"4"},{"key":"2_CR45","doi-asserted-by":"publisher","unstructured":"McKay, D.M., Murray, C.D., Williams, R.R.: Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1215\u20131225 (2019). https:\/\/doi.org\/10.1145\/3313276.3316396","DOI":"10.1145\/3313276.3316396"},{"key":"2_CR46","doi-asserted-by":"crossref","unstructured":"Meyer, A., McCreight, E.: Computationally complex and pseudo-random zero-one valued functions. In: Theory of Machines and Computations, pp. 19\u201342. Elsevier (1971)","DOI":"10.1016\/B978-0-12-417750-5.50006-3"},{"issue":"4","key":"2_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2017.v013a004","volume":"13","author":"C Murray","year":"2017","unstructured":"Murray, C., Williams, R.: On the (non) NP-hardness of computing circuit complexity. Theory Comput. 13(4), 1\u201322 (2017). https:\/\/doi.org\/10.4086\/toc.2017.v013a004","journal-title":"Theory Comput."},{"key":"2_CR48","doi-asserted-by":"publisher","unstructured":"Oliveira, I., Santhanam, R.: Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness. In: 32nd Conference on Computational Complexity, CCC. LIPIcs, vol. 79, pp. 18:1\u201318:49. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2017.18","DOI":"10.4230\/LIPIcs.CCC.2017.18"},{"key":"2_CR49","doi-asserted-by":"publisher","unstructured":"Oliveira, I.C., Pich, J., Santhanam, R.: Hardness magnification near state-of-the-art lower bounds. In: 34th Computational Complexity Conference (CCC). LIPIcs, vol. 137, pp. 27:1\u201327:29. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2019.27","DOI":"10.4230\/LIPIcs.CCC.2019.27"},{"key":"2_CR50","doi-asserted-by":"publisher","unstructured":"Oliveira, I.C., Santhanam, R.: Hardness magnification for natural problems. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 65\u201376 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00016","DOI":"10.1109\/FOCS.2018.00016"},{"issue":"1","key":"2_CR51","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/174644.174648","volume":"41","author":"P Orponen","year":"1994","unstructured":"Orponen, P., Ko, K., Schoning, U., Watanabe, O.: Instance complexity. J. ACM 41(1), 96\u2013121 (1994). https:\/\/doi.org\/10.1145\/174644.174648","journal-title":"J. ACM"},{"key":"2_CR52","doi-asserted-by":"publisher","unstructured":"Paul, W.J., Seiferas, J.I., Simon, J.: An information-theoretic approach to time bounds for on-line computation (preliminary version). In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC 1980, pp. 357\u2013367. ACM, New York (1980). https:\/\/doi.org\/10.1145\/800141.804685 , see also [53]","DOI":"10.1145\/800141.804685"},{"issue":"2","key":"2_CR53","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/0022-0000(81)90009-X","volume":"23","author":"WJ Paul","year":"1981","unstructured":"Paul, W.J., Seiferas, J.I., Simon, J.: An information-theoretic approach to time bounds for on-line computation. J. Comput. Syst. Sci. 23(2), 108\u2013126 (1981). https:\/\/doi.org\/10.1016\/0022-0000(81)90009-X","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR54","doi-asserted-by":"publisher","unstructured":"Peterson, G.L.: Succinct representation, random strings, and complexity classes. In: 21st Annual Symposium on Foundations of Computer Science (FOCS), pp. 86\u201395 (1980). https:\/\/doi.org\/10.1109\/SFCS.1980.42","DOI":"10.1109\/SFCS.1980.42"},{"issue":"4","key":"2_CR55","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L Pitt","year":"1988","unstructured":"Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965\u2013984 (1988). https:\/\/doi.org\/10.1145\/48014.63140","journal-title":"J. ACM"},{"issue":"1","key":"2_CR56","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L Pitt","year":"1993","unstructured":"Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. J. ACM 40(1), 95\u2013142 (1993). https:\/\/doi.org\/10.1145\/138027.138042","journal-title":"J. ACM"},{"key":"2_CR57","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ipl.2017.07.005","volume":"128","author":"M Rudow","year":"2017","unstructured":"Rudow, M.: Discrete logarithm and minimum circuit size. Inf. Process. Lett. 128, 1\u20134 (2017). https:\/\/doi.org\/10.1016\/j.ipl.2017.07.005","journal-title":"Inf. Process. Lett."},{"key":"2_CR58","doi-asserted-by":"publisher","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 330\u2013335 (1983). https:\/\/doi.org\/10.1145\/800061.808762","DOI":"10.1145\/800061.808762"},{"issue":"4","key":"2_CR59","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/MAHC.1984.10036","volume":"6","author":"BA Trakhtenbrot","year":"1984","unstructured":"Trakhtenbrot, B.A.: A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Ann. Hist. Comput. 6(4), 384\u2013400 (1984)","journal-title":"IEEE Ann. Hist. Comput."},{"key":"2_CR60","volume-title":"Kolmogorov Complexity and Computational Complexity","author":"O Watanabe","year":"2012","unstructured":"Watanabe, O.: Kolmogorov Complexity and Computational Complexity, 1st edn. Springer, Heidelberg (2012)","edition":"1"},{"key":"2_CR61","doi-asserted-by":"publisher","unstructured":"Wilber, R.E.: Randomness and the density of hard problems. In: 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 335\u2013342 (1983). https:\/\/doi.org\/10.1109\/SFCS.1983.49","DOI":"10.1109\/SFCS.1983.49"},{"key":"2_CR62","doi-asserted-by":"publisher","unstructured":"Yao, A.C.: Theory and applications of trapdoor functions (extended abstract). In: 23rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 80\u201391 (1982). https:\/\/doi.org\/10.1109\/SFCS.1982.45","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","Complexity and Approximation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-41672-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T05:33:59Z","timestamp":1614490439000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-41672-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030416713","9783030416720"],"references-count":62,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-41672-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"21 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}