{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:55Z","timestamp":1759638895612,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T00:00:00Z","timestamp":1492560000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s00037-017-0154-2","type":"journal-article","created":{"date-parts":[[2017,4,19]],"date-time":"2017-04-19T09:29:31Z","timestamp":1492594171000},"page":"31-61","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Short lists with short programs in short time"],"prefix":"10.1007","volume":"27","author":[{"given":"Bruno","family":"Bauwens","sequence":"first","affiliation":[]},{"given":"Anton","family":"Makhlin","sequence":"additional","affiliation":[]},{"given":"Nikolay","family":"Vereshchagin","sequence":"additional","affiliation":[]},{"given":"Marius","family":"Zimand","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,19]]},"reference":[{"key":"154_CR1","unstructured":"B. Bauwens (2010). Computability in statistical hypotheses testing, and characterizations of independence and directed influences in time series using Kolmogorov complexity. Ph.D. thesis, Ghent University, Faculty of Engineering."},{"key":"154_CR2","doi-asserted-by":"crossref","unstructured":"B. Bauwens, A. Makhlin, N. Vereshchagin & M. Zimand (2013). Short lists with short programs in short time. In the 28th IEEE Conference in Computational Complexity, Stanford, CA, June 5\u20137, 2013, 98\u2013108.","DOI":"10.1109\/CCC.2013.19"},{"issue":"02","key":"154_CR3","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1017\/jsl.2014.15","volume":"79","author":"B. Bauwens","year":"2014","unstructured":"Bauwens B., Shen A. (2014) Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity. The Journal of Symbolic Logic 79(02): 620\u2013632","journal-title":"The Journal of Symbolic Logic"},{"issue":"2","key":"154_CR4","doi-asserted-by":"crossref","first-page":"501","DOI":"10.2178\/jsl\/1146620156","volume":"71","author":"R. Beigel","year":"2006","unstructured":"Beigel R., Buhrman H.M., Fejer P., Fortnow L., Grabowski P., Longpre L., Muchnik A., Stephan F., Torenvliet L. (2006) Enumerations of the Kolmogorov Function. The Journal of Symbolic Logic 71(2): 501\u2013528","journal-title":"The Journal of Symbolic Logic"},{"key":"154_CR5","doi-asserted-by":"crossref","unstructured":"H. Buhrman, L. Fortnow & S. Laplante (2001). Resource-Bounded Kolmogorov Complexity Revisited. SIAM Journal on Computing 31(3), 887\u2013905.","DOI":"10.1137\/S009753979834388X"},{"key":"154_CR6","doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. M. Hitchcock, A. Pavan, N. V. Vinodchandran & F. Wang (2011). Extracting Kolmogorov complexity with applications to dimension zero-one laws. Information and Computation 209(4), 627\u2013636.","DOI":"10.1016\/j.ic.2010.09.006"},{"key":"154_CR7","first-page":"1477","volume":"15","author":"P. Gacs","year":"1974","unstructured":"Gacs P. (1974) On the symmetry of algorithmic information. Soviet Mathematical Doklady 15: 1477\u20131480","journal-title":"Soviet Mathematical Doklady"},{"key":"154_CR8","doi-asserted-by":"crossref","unstructured":"P. Hall (1935). On representatives of subsets. Journal of the London Mathematical Society 1(10), 26\u201330.","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"154_CR9","doi-asserted-by":"crossref","unstructured":"J. M. Hitchcock, A. Pavan & N. V. Vinodchandran (2011). Kolmogorov Complexity in Randomness Extraction. Transactions on Computation Theory 3(1), 1.","DOI":"10.1145\/2003685.2003686"},{"key":"154_CR10","doi-asserted-by":"crossref","unstructured":"T. Kova\u030bri, V.T. S\u00f2s & P. Tur\u00e0n (1954). On a problem of K. Zarankiewicz. Colloquium Mathematicae 3, 50\u201357.","DOI":"10.4064\/cm-3-1-50-57"},{"key":"154_CR11","doi-asserted-by":"crossref","unstructured":"A. H. Lachlan (1970). On Some Games Which Are Relevant to the Theory of Recursively Enumerable Sets. Annals of Mathematics 91(2), 291\u2013310. http:\/\/www.jstor.org\/stable\/1970579 .","DOI":"10.2307\/1970579"},{"issue":"1\u20132","key":"154_CR12","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0304-3975(01)00033-0","volume":"271","author":"A.A. Muchnik","year":"2002","unstructured":"Muchnik A.A. (2002) Conditional complexity and codes. Theoretical Computer Science 271(1\u20132): 97\u2013109","journal-title":"Theoretical Computer Science"},{"key":"154_CR13","unstructured":"A. A. Muchnik, I. Mezhirov, A. Shen & N. Vereshchagin (2010). Game interpretation of Kolmogorov complexity. Unpublished."},{"key":"154_CR14","doi-asserted-by":"crossref","unstructured":"D. Musatov (2011). Improving the Space-Bounded Version of Muchnik\u2019s Conditional Complexity Theorem via \u201cNaive\" Derandomization. In International Computer Science Symposium in Russia, 64\u201376.","DOI":"10.1007\/978-3-642-20712-9_6"},{"key":"154_CR15","doi-asserted-by":"crossref","unstructured":"D. Musatov (2012). Space-Bounded Kolmogorov Extractors. In International Computer Science Symposium in Russia, 266\u2013277.","DOI":"10.1007\/978-3-642-30642-6_25"},{"key":"154_CR16","doi-asserted-by":"crossref","unstructured":"D. Musatov, A. E. Romashchenko & A. Shen (2011). Variations on Muchnik\u2019s Conditional Complexity Theorem. Theory of Computation Systems 49(2), 227\u2013245.","DOI":"10.1007\/s00224-011-9321-z"},{"key":"154_CR17","doi-asserted-by":"crossref","unstructured":"J. Radhakrishnan & A. Ta-Shma (2000). Tight bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics 13(1), 2\u201324.","DOI":"10.1137\/S0895480197329508"},{"issue":"2","key":"154_CR18","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/BF01762189","volume":"8","author":"Schnorr C.P.","year":"1975","unstructured":"C.P. Schnorr (1975) Optimal Enumerations and Optimal G\u00f6del Numberings. Mathematical Systems Theory 8(2): 182\u2013191","journal-title":"Mathematical Systems Theory"},{"key":"154_CR19","doi-asserted-by":"crossref","unstructured":"A. Shen (2012). Game arguments in computability theory and algorithmic information theory. In Conference on Computability in Europe. Springer, Berlin Heidelberg.","DOI":"10.1007\/978-3-642-30870-3_66"},{"key":"154_CR20","doi-asserted-by":"crossref","unstructured":"M. Sipser (1983). A Complexity Theoretic Approach to Randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, 330\u2013335.","DOI":"10.1145\/800061.808762"},{"key":"154_CR21","unstructured":"F. Stephan (2013). Personal Communication."},{"key":"154_CR22","doi-asserted-by":"crossref","unstructured":"A. Ta-Shma, C. Umans & D. Zuckerman (2007). Lossless Condensers, Unbalanced Expanders, And Extractors. Combinatorica 27(2), 213\u2013240.","DOI":"10.1007\/s00493-007-0053-2"},{"key":"154_CR23","doi-asserted-by":"crossref","unstructured":"J. Teutsch (2014). Short lists for shortest descriptions in short time. Computational Complexity 23(4), 565\u2013583. http:\/\/dx.doi.org\/10.1007\/s00037-014-0090-3 .","DOI":"10.1007\/s00037-014-0090-3"},{"key":"154_CR24","unstructured":"N. Vereshchagin (2008). Kolmogorov complexity and Games. Bulletin of the European Association for Theoretical Computer Science 94, 51\u201383."},{"issue":"3","key":"154_CR25","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s00224-014-9605-1","volume":"58","author":"N. Vereshchagin","year":"2016","unstructured":"Vereshchagin N. (2016) Algorithmic minimal sufficient statistics: a new approach. Theory of Computing Systems 58(3): 463\u2013481","journal-title":"Theory of Computing Systems"},{"key":"154_CR26","unstructured":"M. Zimand (2010a). Possibilities and impossibilities in Kolmogorov complexity extraction. SIGACT News 41(4), 74\u201394."},{"key":"154_CR27","doi-asserted-by":"crossref","unstructured":"M. Zimand (2010b). Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences. Theory of Computing Systems 46(4), 707\u2013722.","DOI":"10.1007\/s00224-009-9214-6"},{"key":"154_CR28","doi-asserted-by":"crossref","unstructured":"M. Zimand (2011). Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors. In IEEE Conference on Computational Complexity, 148\u2013156.","DOI":"10.1109\/CCC.2011.21"},{"issue":"4","key":"154_CR29","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1093\/logcom\/exr053","volume":"23","author":"M. Zimand","year":"2013","unstructured":"Zimand M. (2013) Generating Kolmogorov random strings from sources with limited independence. Journal of Logic and Computation 23(4): 909\u2013924","journal-title":"Journal of Logic and Computation"},{"key":"154_CR30","doi-asserted-by":"crossref","unstructured":"M. Zimand (2014). Short Lists with Short Programs in Short Time - A Short Proof. In Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23\u201327, 2014. Proceedings, 403\u2013408.","DOI":"10.1007\/978-3-319-08019-2_42"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0154-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0154-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0154-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T04:48:29Z","timestamp":1569041309000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0154-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,19]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["154"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0154-2","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2017,4,19]]}}}