{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T03:05:33Z","timestamp":1769223933290,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,12,20]],"date-time":"2021-12-20T00:00:00Z","timestamp":1639958400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2021,12,20]]},"abstract":"<jats:p>This formula can be informally read as follows: the ith messagemi brings us log(1=pi) \"bits of information\" (whatever this means), and appears with frequency pi, so H is the expected amount of information provided by one random message (one sample of the random variable). Moreover, we can construct an optimal uniquely decodable code that requires about H (at most H + 1, to be exact) bits per message on average, and it encodes the ith message by approximately log(1=pi) bits, following the natural idea to use short codewords for frequent messages. This fits well the informal reading of the formula given above, and it is tempting to say that the ith message \"contains log(1=pi) bits of information.\" Shannon himself succumbed to this temptation [46, p. 399] when he wrote about entropy estimates and considers Basic English and James Joyces's book \"Finnegan's Wake\" as two extreme examples of high and low redundancy in English texts. But, strictly speaking, one can speak only of entropies of random variables, not of their individual values, and \"Finnegan's Wake\" is not a random variable, just a specific string. Can we define the amount of information in individual objects?<\/jats:p>","DOI":"10.1145\/3510382.3510389","type":"journal-article","created":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T18:15:15Z","timestamp":1641233715000},"page":"31-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["27 Open Problems in Kolmogorov Complexity"],"prefix":"10.1145","volume":"52","author":[{"given":"Andrei","family":"Romashchenko","sequence":"first","affiliation":[{"name":"Univ. Montpellier"}]},{"given":"Alexander","family":"Shen","sequence":"additional","affiliation":[{"name":"Univ. Montpellier"}]},{"given":"Marius","family":"Zimand","sequence":"additional","affiliation":[{"name":"Towson University"}]}],"member":"320","published-online":{"date-parts":[[2022,1,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.243431"},{"key":"e_1_2_1_2_1","volume-title":"Kolmogorov complexity, and the new complexity landscape around circuit minimization","author":"Allender E.","year":"2021"},{"key":"e_1_2_1_3_1","volume-title":"Proc. International Conference on Information Theoretic Security, 195--210","author":"Antunes L.","year":"2007"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9789-2"},{"key":"e_1_2_1_5_1","volume-title":"Short lists with short programs in short time. Computational Complexity, 27(1), 31--61","author":"Bauwens B.","year":"2018"},{"key":"e_1_2_1_6_1","volume-title":"CoRR, abs\/1311.7278","author":"Bauwens B.","year":"2013"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.32"},{"key":"e_1_2_1_8_1","volume-title":"CoRR, abs\/1911.04268","author":"Bauwens B.","year":"2019"},{"key":"e_1_2_1_9_1","volume-title":"22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 412--421","author":"Buhrman H.","year":"2005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1134\/S0081543811060058"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.04.009"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9791-8"},{"issue":"3","key":"e_1_2_1_13_1","first-page":"887","volume":"31","author":"Buhrman H.","year":"2001","journal-title":"Resource-bounded Kolmogorov complexity revisited. SIAM J. Comput."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.1013138"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.3390\/e13020379"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"e_1_2_1_17_1","first-page":"385","volume":"36","author":"G\u00b4acs P.","year":"1980","journal-title":"Math."},{"issue":"2","key":"e_1_2_1_18_1","first-page":"119","volume":"2","author":"G\u00b4acs P.","year":"1973","journal-title":"Problems of Control and Information Theory"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1974.tb02812.x"},{"key":"e_1_2_1_20_1","volume-title":"Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory. In: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), 44: 1--44:14","author":"G\u00a8urpnar E.","year":"2020"},{"key":"e_1_2_1_21_1","volume-title":"35th Computational Complexity Conference (CCC 2020","author":"Ilango R.","year":"2020"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1677"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2274614"},{"key":"e_1_2_1_24_1","volume-title":"Problemy peredachi informatsii (Problems of Information Transmission), 1(1), 3--11","author":"Kolmogorov A.","year":"1965"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054210"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3357209"},{"key":"e_1_2_1_27_1","first-page":"1","volume":"94","author":"Lu Z.","year":"2021","journal-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP)"},{"key":"e_1_2_1_28_1","volume-title":"Bounding the dimensions of points on a line, Information and Computation, 275, 104601","author":"Lutz N.","year":"2020"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2007.4557201"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.256484"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00033-0"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1134\/S0081543811060125"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1134\/S0032946010010059"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/792764.793398"},{"issue":"2","key":"e_1_2_1_35_1","first-page":"227","volume":"49","author":"Musatov D.","year":"2011","journal-title":"Variations on Muchnik's conditional complexity theorem. Theory Comput. Syst."},{"key":"e_1_2_1_36_1","volume-title":"Multiterminal Secrecy by Public Discussion. Foundations and Trends in Communications and Information Theory, 13(2--3), 129--275 (2016)","author":"Narayan P.","year":"2016"},{"key":"e_1_2_1_37_1","volume-title":"Oxford University Press","author":"Nies A.","year":"2012"},{"key":"e_1_2_1_38_1","volume-title":"13th Conference on Computability in Europe (CiE) 338--350","author":"Novikov G.","year":"2017"},{"key":"e_1_2_1_39_1","volume-title":"36th International Symposium on Theoretical Aspects of Computer Science (STACS), 57:1--57:14","author":"Posobin G.","year":"2019"},{"key":"e_1_2_1_40_1","volume-title":"CoRR, abs\/1104.3207","author":"Razenshteyn I.","year":"2011"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00034-2"},{"issue":"1","key":"e_1_2_1_42_1","first-page":"20","volume":"5","author":"Romashchenko A.","year":"2005","journal-title":"Information Processes"},{"key":"e_1_2_1_43_1","volume-title":"Coding in the fork network in the framework of Kolmogorov complexity. CoRR, abs\/1602.02648","author":"Romashchenko A.","year":"2016"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3356867"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/220"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1973.1055037"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2946364"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-014-0090-3"},{"key":"e_1_2_1_50_1","volume-title":"Algorithmic statistics: forty years later. Computability and Complexity. Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday","author":"Vereshchagin N.","year":"2017"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055346"},{"key":"e_1_2_1_52_1","volume-title":"A first course in information theory","author":"Yeung R.W.","year":"2012"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4310\/CIS.2015.v15.n1.a6"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08019-2_42"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055421"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510382.3510389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3510382.3510389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:45Z","timestamp":1750183785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3510382.3510389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,20]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,20]]}},"alternative-id":["10.1145\/3510382.3510389"],"URL":"https:\/\/doi.org\/10.1145\/3510382.3510389","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2021,12,20]]},"assertion":[{"value":"2022-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}