{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:59Z","timestamp":1781031419018,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"JST ACT-X","award":["JPMJAX24CJ"],"award-info":[{"award-number":["JPMJAX24CJ"]}]},{"name":"JST FOREST","award":["JPMJFR226Y"],"award-info":[{"award-number":["JPMJFR226Y"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800757","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"377-385","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity-Theoretic Universal Inductive Inference"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3101-446X","authenticated-orcid":false,"given":"Shuichi","family":"Hirahara","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4064-1462","authenticated-orcid":false,"given":"Mikito","family":"Nanashima","sequence":"additional","affiliation":[{"name":"Institute of Science Tokyo, Tokyo, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.033"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.12"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.35"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2507.13222"},{"key":"e_1_3_2_1_5_1","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Blier L\u00e9onard","year":"2018","unstructured":"L\u00e9onard Blier and Yann Ollivier. 2018. The Description Length of Deep Learning models. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr\u00e9al, Canada. 2220\u20132230."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446974"},{"key":"e_1_3_2_1_7_1","volume-title":"Sequential Learning of Neural Networks for Prequential MDL. In The Eleventh International Conference on Learning Representations, ICLR 2023","author":"Bornschein J\u00f6rg","year":"2023","unstructured":"J\u00f6rg Bornschein, Yazhe Li, and Marcus Hutter. 2023. Sequential Learning of Neural Networks for Prequential MDL. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net. https:\/\/openreview.net\/forum?id=dMMPUvNSYJr"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/2981683"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/3318616"},{"key":"e_1_3_2_1_10_1","volume-title":"Language Modeling Is Compression. In The Twelfth International Conference on Learning Representations, ICLR 2024","author":"Del\u00e9tang Gr\u00e9goire","year":"2024","unstructured":"Gr\u00e9goire Del\u00e9tang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. 2024. Language Modeling Is Compression. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. https:\/\/openreview.net\/forum?id=jznbgiynus"},{"key":"e_1_3_2_1_11_1","volume-title":"Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022","author":"Goel Surbhi","year":"2022","unstructured":"Surbhi Goel, Sham M. Kakade, Adam Kalai, and Cyril Zhang. 2022. Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022."},{"key":"e_1_3_2_1_12_1","unstructured":"Halley Goldberg and Valentine Kabanets. 2021. A Simplified Proof of Hirahara\u2019s Theorem. manuscript"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2023.12"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2022.16"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/4643.001.0001"},{"key":"e_1_3_2_1_16_1","volume-title":"The Thirty Seventh Annual Conference on Learning Theory","author":"Han Yanjun","year":"2024","unstructured":"Yanjun Han, Tianze Jiang, and Yihong Wu. 2024. Prediction from compression for models with infinite memory, with applications to hidden Markov and renewal processes. In The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, Shipra Agrawal and Aaron Roth (Eds.) (Proceedings of Machine Learning Research). PMLR, 2270\u20132307. https:\/\/proceedings.mlr.press\/v247\/han24a.html"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00032"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00014"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2020.20"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451065"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00095"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2022.26"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585138"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00030"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78011-0_9"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00078"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.25"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00033"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS). 38:1\u201338:23","author":"Hirahara Shuichi","year":"2022","unstructured":"Shuichi Hirahara and Rahul Santhanam. 2022. Errorless versus Error-prone Average-case Complexity. In Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS). 38:1\u201338:23."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/b138233"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Marcus Hutter David Quarel and Elliot Catt. 2024. An Introduction to Universal Artificial Intelligence. http:\/\/www.hutter1.net\/ai\/uaibook2.htm","DOI":"10.1201\/9781003460299"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00048"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1995.514853"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89604"},{"key":"e_1_3_2_1_35_1","volume-title":"TR25-089","author":"Kabanets Valentine","year":"2025","unstructured":"Valentine Kabanets and Antonina Kolokolova. 2025. Chain Rules for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex., TR25-089 (2025), ECCC:TR25-089. https:\/\/eccc.weizmann.ac.il\/report\/2025\/089\/"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195155"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90204-M"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1120"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.720534"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143926"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63140"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90223-2"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90131-7"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_46_1","first-page":"524","volume-title":"COLT 2010 - The 23rd Conference on Learning Theory","author":"Xiao David","year":"2010","unstructured":"David Xiao. 2010. Learning to Create is as Hard as Learning to Appreciate. In COLT 2010 - The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, Adam Tauman Kalai and Mehryar Mohri (Eds.). Omnipress, 516\u2013528. http:\/\/colt2010.haifa.il.ibm.com\/papers\/COLT2010proceedings.pdf#page=524"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:59:25Z","timestamp":1781027965000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":47,"alternative-id":["10.1145\/3798129.3800757","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800757","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}