{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:15:07Z","timestamp":1764339307792,"version":"3.46.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T00:00:00Z","timestamp":1764288000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1445755, 1545028, and 1900716"],"award-info":[{"award-number":["1445755, 1545028, and 1900716"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>We investigate the relationship between algorithmic fractal dimensions and the classical local fractal dimensions of outer measures in Euclidean spaces. We introduce global and local optimality conditions for lower semicomputable outer measures. We prove that globally optimal outer measures exist. Our main theorem states that the classical local fractal dimensions of any locally optimal outer measure coincide exactly with the algorithmic fractal dimensions. Our proof uses an especially convenient locally optimal outer measure \u03ba defined in terms of Kolmogorov complexity. We discuss implications for point-to-set principles.<\/jats:p>","DOI":"10.1145\/3733607","type":"journal-article","created":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T07:12:46Z","timestamp":1746601966000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithmically Optimal Outer Measures"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1004-3891","authenticated-orcid":false,"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[{"name":"Computer Science, Iowa State University","place":["Ames, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8399-8678","authenticated-orcid":false,"given":"Neil","family":"Lutz","sequence":"additional","affiliation":[{"name":"Computer Science, Swarthmore College","place":["Swarthmore, United States"]}]}],"member":"320","published-online":{"date-parts":[[2025,11,28]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703446912"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255629826"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781316460238"},{"key":"e_1_3_2_5_2","first-page":"404","article-title":"\u00dcber das lineare Ma\u00df von Punktmengen\u2014eine Verallgemeinerung des L\u00e4ngenbegriffs","author":"Carath\u00e9odory Constantin","year":"1914","unstructured":"Constantin Carath\u00e9odory. 1914. \u00dcber das lineare Ma\u00df von Punktmengen\u2014eine Verallgemeinerung des L\u00e4ngenbegriffs. Nachrichten Von Der Gesellschaft der Wissenschaften zu G\u00f6ttingen, Mathematisch-Physikalische Klasse (1914), 404\u2013426. Translated as On the Linear Measure of Point Sets\u2014a Generalization of the Concept of Length. In Classics on Fractals. Gerald A. Edgar (Ed.), Addison Wesley, 1993.","journal-title":"Nachrichten Von Der Gesellschaft der Wissenschaften zu G\u00f6ttingen, Mathematisch-Physikalische Klasse"},{"key":"e_1_3_2_6_2","volume-title":"Vorlesungen \u00fcber Reele Funktionen","author":"Carath\u00e9odory Constantin","year":"1918","unstructured":"Constantin Carath\u00e9odory. 1918. Vorlesungen \u00fcber Reele Funktionen. Teubner, Leipzig."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2786566"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100073758"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1205766"},{"key":"e_1_3_2_10_2","volume-title":"Techniques in Fractal Geometry","author":"Falconer Kenneth J.","year":"1997","unstructured":"Kenneth J. Falconer. 1997. Techniques in Fractal Geometry. Wiley."},{"key":"e_1_3_2_11_2","volume-title":"Fractal Geometry: Mathematical Foundations and Applications (3rd ed.)","author":"Falconer Kenneth J.","year":"2014","unstructured":"Kenneth J. Falconer. 2014. Fractal Geometry: Mathematical Foundations and Applications (3rd ed.). Wiley."},{"key":"e_1_3_2_12_2","first-page":"1","article-title":"Potential d\u2019equilibre et capacit\u00e9 des ensembles avec quelques applications a la the\u00f3rie des fonctions","volume":"3","author":"Frostman Otto","year":"1935","unstructured":"Otto Frostman. 1935. Potential d\u2019equilibre et capacit\u00e9 des ensembles avec quelques applications a la the\u00f3rie des fonctions. Meddelanden fr\u00e5n Lunds Universitets Matematiska Seminarium 3 (1935), 1\u2013118.","journal-title":"Meddelanden fr\u00e5n Lunds Universitets Matematiska Seminarium"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457179"},{"issue":"3","key":"e_1_3_2_14_2","first-page":"437","article-title":"Lectures on dynamics, fractal geometry, and metric number theory","volume":"8","author":"Hochman Michael","year":"2014","unstructured":"Michael Hochman. 2014. Lectures on dynamics, fractal geometry, and metric number theory. Journal of Modern Dynamics 8, 3\u20134 (2014), 437\u2013497.","journal-title":"Journal of Modern Dynamics"},{"issue":"5","key":"e_1_3_2_15_2","first-page":"1413","article-title":"On the notion of a random sequence","volume":"14","author":"Levin Leonid A.","year":"1973","unstructured":"Leonid A. Levin. 1973. On the notion of a random sequence. Soviet Mathematics Doklady 14, 5 (1973), 1413\u20131416.","journal-title":"Soviet Mathematics Doklady"},{"issue":"3","key":"e_1_3_2_16_2","first-page":"30","article-title":"Laws of information conservation (nongrowth) and aspects of the foundation of probability theory","volume":"10","author":"Levin Leonid A.","year":"1974","unstructured":"Leonid A. Levin. 1974. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii 10, 3 (1974), 30\u201335.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/3357209"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00187-1"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3201783"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-41672-0_4"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2023.105078"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/070684689"},{"key":"e_1_3_2_23_2","volume-title":"Algorithmic Information, Fractal Geometry, and Distributed Dynamics","author":"Lutz Neil","year":"2017","unstructured":"Neil Lutz. 2017. Algorithmic Information, Fractal Geometry, and Distributed Dynamics. Ph.D. Dissertation. Rutgers University."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460948"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104601"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105137"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511623813"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00343-5"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68546-5_12"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/1572527"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004120000328"},{"key":"e_1_3_2_32_2","volume-title":"Computability and Fractal Dimension","author":"Reimann Jan","year":"2004","unstructured":"Jan Reimann. 2004. Computability and Fractal Dimension. Ph.D. Dissertation. Heidelberg University."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00035-4"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/126"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3733607","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3733607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:10:15Z","timestamp":1764339015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,28]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3733607"],"URL":"https:\/\/doi.org\/10.1145\/3733607","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,11,28]]},"assertion":[{"value":"2024-01-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-05","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}