{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:47:44Z","timestamp":1725587264401},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_25","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"293-304","source":"Crossref","is-referenced-by-count":2,"title":["Limits on the Computational Power of Random Strings"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luke","family":"Friedman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Gasarch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","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":"25_CR2","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":"25_CR3","unstructured":"Allender, E., Friedman, L., Gasarch, W.: Limits on the computational power of random strings. Technical Report TR10-139, Electronic Colloquium on Computational Complexity (2010)"},{"key":"25_CR4","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., Kouck\u00fd, M., Ronneburger, D., Roy, S.: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences\u00a077, 14\u201340 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR5","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\u00a03, 307\u2013318 (1993)","journal-title":"Computational Complexity"},{"issue":"6","key":"25_CR6","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.1137\/S0097539793238140","volume":"23","author":"R.V. Book","year":"1994","unstructured":"Book, R.V.: On languages reducible to algorithmically random languages. SIAM Journal on Computing\u00a023(6), 1275\u20131282 (1994)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"25_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF01578842","volume":"27","author":"R.V. Book","year":"1994","unstructured":"Book, R.V., Lutz, J., Wagner, K.W.: An observation on probability versus randomness with applications to complexity classes. Mathematical Systems Theory\u00a027(3), 201\u2013209 (1994)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"25_CR8","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1051\/ita\/1996300201231","volume":"30","author":"R.V. Book","year":"1996","unstructured":"Book, R.V., Mayordomo, E.: On the robustness of ALMOST-r. RAIRO Informatique Th\u00e9orique et Applications\u00a030(2), 123\u2013133 (1996)","journal-title":"RAIRO Informatique Th\u00e9orique et Applications"},{"key":"25_CR9","first-page":"58","volume-title":"25th IEEE Conference on Computational Complexity (CCC)","author":"H. Buhrman","year":"2010","unstructured":"Buhrman, H., Fortnow, L., Koucky, M., Loff, B.: Derandomizing from random strings. In: 25th IEEE Conference on Computational Complexity (CCC), pp. 58\u201363. IEEE Computer Society Press, Los Alamitos (2010)"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-540-85363-3_37","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"D. Gutfreund","year":"2008","unstructured":"Gutfreund, D., Vadhan, S.P.: Limitations of hardness vs. Randomness under uniform reductions. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 469\u2013482. Springer, Heidelberg (2008)"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-13962-8_22","volume-title":"Programs, Proofs, Processes","author":"J.M. Hitchcock","year":"2010","unstructured":"Hitchcock, J.M.: Lower bounds for reducibility to the kolmogorov random strings. In: Ferreira, F., L\u00f6we, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol.\u00a06158, pp. 195\u2013200. Springer, Heidelberg (2010)"},{"issue":"4","key":"25_CR12","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1006\/jcss.2001.1780","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs. time: de-randomization under a uniform assumption. J. Comput. Syst. Sci.\u00a063(4), 672\u2013688 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Cai, J.-Y.: Circuit minimization problem. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 73\u201379 (2000)","DOI":"10.1145\/335305.335314"},{"key":"25_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49820-1","volume-title":"Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"2008","unstructured":"Li, M., Vitanyi, P.: Introduction to Kolmogorov Complexity and its Applications, 3rd edn. Springer, Heidelberg (2008)","edition":"3"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0304-3975(01)00028-7","volume":"271","author":"A.A. Muchnik","year":"2002","unstructured":"Muchnik, A.A., Positselsky, S.: Kolmogorov entropy in the context of computability theory. Theoretical Computer Science\u00a0271, 15\u201335 (2002)","journal-title":"Theoretical Computer Science"},{"key":"25_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-24638-1_1","volume-title":"Theory of Cryptography","author":"O. Reingold","year":"2004","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.P.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 1\u201320. Springer, Heidelberg (2004)"},{"issue":"4","key":"25_CR17","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"L. Trevisan","year":"2007","unstructured":"Trevisan, L., Vadhan, S.P.: Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity\u00a016(4), 331\u2013364 (2007)","journal-title":"Computational Complexity"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T07:52:56Z","timestamp":1553845976000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}