{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:10:37Z","timestamp":1740287437813,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405436"},{"type":"electronic","value":"9783540450771"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45077-1_28","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T20:53:34Z","timestamp":1277499214000},"page":"303-310","source":"Crossref","is-referenced-by-count":3,"title":["Using Depth to Capture Average-Case Complexity"],"prefix":"10.1007","author":[{"given":"Lu\u00eds","family":"Antunes","sequence":"first","affiliation":[]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Antunes, L., Fortnow, L., van Melkebeek, D.: Computational depth. In: Proceedings of the 16th IEEE Conference on Computational Complexity, pp. 266\u2013273 (2001)","DOI":"10.1109\/CCC.2001.933893"},{"issue":"2","key":"28_CR2","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0022-0000(92)90019-F","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the theory of average case complexity. J. Computer System Sci.\u00a044(2), 193\u2013219 (1992)","journal-title":"J. Computer System Sci."},{"key":"28_CR3","first-page":"227","volume-title":"The Universal Turing Machine: A Half-Century Survey","author":"C.H. Bennett","year":"1988","unstructured":"Bennett, C.H.: Logical depth and physical complexity. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp. 227\u2013257. Oxford University Press, Oxford (1988)"},{"issue":"4","key":"28_CR4","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing\u00a028(4), 1364\u20131396 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"28_CR5","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L.A. Levin","year":"1986","unstructured":"Levin, L.A.: Average case complete problems. SIAM Journal on Computing\u00a015(1), 285\u2013286 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR6","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\u00a061, 15\u201337 (1984)","journal-title":"Information and Control"},{"issue":"3","key":"28_CR7","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0020-0190(92)90138-L","volume":"42","author":"M. Li","year":"1992","unstructured":"Li, M., Vitanyi, P.M.B.: Average case complexity under the universal distribution equals worst-case complexity. Information Processing Letters\u00a042(3), 145\u2013149 (1992)","journal-title":"Information Processing Letters"},{"key":"28_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An introduction to Kolmogorov complexity and its applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An introduction to Kolmogorov complexity and its applications, 2nd edn. Springer, Heidelberg (1997)","edition":"2"},{"issue":"1","key":"28_CR9","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1137\/0222012","volume":"22","author":"P.B. Miltersen","year":"1993","unstructured":"Miltersen, P.B.: The complexity of malign measures. SIAM Journal on Computing\u00a022(1), 147\u2013156 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Schuler, R.: Universal distributions and time-bounded Kolmogorov complexity. In: Proc. 16th Annual Symposium on Theoretical Aspects of Computer Science, pp. 434\u2013443 (1999)","DOI":"10.1007\/3-540-49116-3_41"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Wang, J.: Average-case computational complexity theory. In: Selman, A.L. (ed.) Complexity Theory Retrospective, vol.\u00a02 (1997)","DOI":"10.1007\/978-1-4612-1872-2_12"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45077-1_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T07:52:06Z","timestamp":1740210726000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45077-1_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405436","9783540450771"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45077-1_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}