{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T08:42:58Z","timestamp":1725698578534},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325885"},{"type":"electronic","value":"9783642325892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32589-2_11","type":"book-chapter","created":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T08:44:32Z","timestamp":1343810672000},"page":"88-99","source":"Crossref","is-referenced-by-count":4,"title":["Reductions to the Set of Random Strings: The Resource-Bounded Case"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Harry","family":"Buhrman","sequence":"additional","affiliation":[]},{"given":"Luke","family":"Friedman","sequence":"additional","affiliation":[]},{"given":"Bruno","family":"Loff","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-642-30870-3_2","volume-title":"How the World Computes","author":"E. Allender","year":"2012","unstructured":"Allender, E.: Curiouser and Curiouser: The Link between Incompressibility and Complexity. In: Cooper, S.B., Dawar, A., L\u00f6we, B. (eds.) CiE 2012. LNCS, vol.\u00a07318, pp. 11\u201316. Springer, Heidelberg (2012)"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Buhrman, H., Friedman, L., Loff, B.: Reductions to the set of random strings:the resource-bounded case. Technical Report TR12-054, ECCC (2012)","DOI":"10.1007\/978-3-642-32589-2_11"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.apal.2005.06.003","volume":"138","author":"E. Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M.: What can be efficiently reduced to the Kolmogorov-random strings? Annals of Pure and Applied Logic\u00a0138, 2\u201319 (2006)","journal-title":"Annals of Pure and Applied Logic"},{"key":"11_CR4","doi-asserted-by":"publisher","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 Journal on Computing\u00a035, 1467\u20131493 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR5","unstructured":"Allender, E., Davie, G., Friedman, L., Hopkins, S.B., Tzameret, I.: Kolmogorov complexity, circuits, and the strength of formal theories of arithmetic. Technical Report TR12-028, ECCC (2012) (submitted for publication)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Allender, E., Friedman, L., Gasarch, W.: Limits on the computational power of random strings. Information and Computation (to appear, 2012); special issue on ICALP 2011, See also ECCC TR10-139","DOI":"10.1016\/j.ic.2011.09.008"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar, J.L., D\u00edas, J., Gabarr\u00f3, J.: Structural Complexity I. Springer (1988)","DOI":"10.1007\/978-3-642-97062-7"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L., Kouck\u00fd, M., Loff, B.: Derandomizing from random strings. In: 25th IEEE Conference on Computational Complexity (CCC), pp. 58\u201363. IEEE (2010)","DOI":"10.1109\/CCC.2010.15"},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-540-31856-9_34","volume-title":"STACS 2005","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Fortnow, L., Newman, I., Vereshchagin, N.K.: Increasing Kolmogorov Complexity. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 412\u2013421. Springer, Heidelberg (2005)"},{"issue":"3","key":"11_CR10","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. J. Comput. Syst. Sci.\u00a054(3), 393\u2013399 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"11_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s002249910008","volume":"33","author":"D.W. Juedes","year":"2000","unstructured":"Juedes, D.W., Lutz, J.H.: Modeling time-bounded prefix Kolmogorov complexity. Theory of Computing Systems\u00a033(2), 111\u2013123 (2000)","journal-title":"Theory of Computing Systems"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Li, M., Vitanyi, P.: Introduction to Kolmogorov Complexity and its Applications, 3rd edn. Springer (2008)","DOI":"10.1007\/978-0-387-49820-1"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32589-2_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:10:10Z","timestamp":1606187410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32589-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325885","9783642325892"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32589-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}