{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T17:17:23Z","timestamp":1764350243059,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,7,9]],"date-time":"2015-07-09T00:00:00Z","timestamp":1436400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"the Isaac Newton Institute for Mathematical Sciences at the University of Cambridge"},{"name":"National Science Foundation","award":["0652569, 1143830, and 124705"],"award-info":[{"award-number":["0652569, 1143830, and 124705"]}]},{"DOI":"10.13039\/100006961","name":"Caltech","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006961","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,7,9]]},"abstract":"<jats:p>\n            We define the lower and upper\n            <jats:italic>mutual dimensions<\/jats:italic>\n            <jats:italic>mdim<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            :\n            <jats:italic>y<\/jats:italic>\n            ) and\n            <jats:italic>Mdim<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            :\n            <jats:italic>y<\/jats:italic>\n            ) between any two points\n            <jats:italic>x<\/jats:italic>\n            and\n            <jats:italic>y<\/jats:italic>\n            in Euclidean space. Intuitively, these are the lower and upper densities of the algorithmic information shared by\n            <jats:italic>x<\/jats:italic>\n            and\n            <jats:italic>y<\/jats:italic>\n            . We show that these quantities satisfy the main desiderata for a satisfactory measure of mutual algorithmic information. Our main theorem, the\n            <jats:italic>data processing inequality<\/jats:italic>\n            for mutual dimension, says that if\n            <jats:italic>f<\/jats:italic>\n            : R\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sup>\n            \u2192 R\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            is computable and Lipschitz, then the inequalities\n            <jats:italic>mdim<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ):\n            <jats:italic>y<\/jats:italic>\n            ) \u2264\n            <jats:italic>mdim<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            :\n            <jats:italic>y<\/jats:italic>\n            ) and\n            <jats:italic>Mdim<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            ):\n            <jats:italic>y<\/jats:italic>\n            ) \u2264\n            <jats:italic>Mdim<\/jats:italic>\n            (\n            <jats:italic>x<\/jats:italic>\n            :\n            <jats:italic>y<\/jats:italic>\n            ) hold for all\n            <jats:italic>x<\/jats:italic>\n            \u2208 R\n            <jats:sup>\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sup>\n            and\n            <jats:italic>y<\/jats:italic>\n            \u2208 R\n            <jats:sup>\n              <jats:italic>t<\/jats:italic>\n            <\/jats:sup>\n            . We use this inequality and related inequalities that we prove in like fashion to establish conditions under which various classes of computable functions on Euclidean space preserve or otherwise transform mutual dimensions between points.\n          <\/jats:p>","DOI":"10.1145\/2786566","type":"journal-article","created":{"date-parts":[[2015,7,10]],"date-time":"2015-07-10T14:10:15Z","timestamp":1436537415000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Mutual Dimension"],"prefix":"10.1145","volume":"7","author":[{"given":"Adam","family":"Case","sequence":"first","affiliation":[{"name":"Iowa State University, Ames, IA USA"}]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[{"name":"Iowa State University, Ames, IA USA"}]}],"member":"320","published-online":{"date-parts":[[2015,7,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703446912"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177704583"},{"key":"e_1_2_1_3_1","first-page":"318","article-title":"Computing over the reals: Foundations for scientific computing","volume":"53","author":"Braverman Mark","year":"2006","unstructured":"Mark Braverman and Stephen Cook . 2006 . Computing over the reals: Foundations for scientific computing . Notices of the American Mathematical Society 53 , 3 (2006), 318 -- 329 . Mark Braverman and Stephen Cook. 2006. Computing over the reals: Foundations for scientific computing. Notices of the American Mathematical Society 53, 3 (2006), 318--329.","journal-title":"Notices of the American Mathematical Society"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9306-3"},{"key":"e_1_2_1_5_1","volume-title":"Thomas","author":"Cover Thomas R.","year":"2006","unstructured":"Thomas R. Cover and Joy A . Thomas . 2006 . Elements of Information Theory (2nd ed.). John Wiley & Sons , Hoboken, NJ. 776 pages. Thomas R. Cover and Joy A. Thomas. 2006. Elements of Information Theory (2nd ed.). John Wiley & Sons, Hoboken, NJ. 776 pages."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05912-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/0470013850"},{"key":"e_1_2_1_8_1","first-page":"1477","article-title":"On the symmetry of algorithmic information","volume":"15","author":"G\u00e1cs Peter","year":"1974","unstructured":"Peter G\u00e1cs . 1974 . On the symmetry of algorithmic information . Soviet Mathematics Doklady 15 , 5 (1974), 1477 -- 1480 . Correction, Ibid., 15:1480, 1974. Peter G\u00e1cs. 1974. On the symmetry of algorithmic information. Soviet Mathematics Doklady 15, 5 (1974), 1477--1480. Correction, Ibid., 15:1480, 1974.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.01.004"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.63"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1677"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1122-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.045"},{"volume-title":"Complexity Theory of Real Functions","author":"I Ko.","key":"e_1_2_1_14_1","unstructured":"Ker- I Ko. 1991. Complexity Theory of Real Functions . Birkh\u00e4user , Boston, MA . 310 pages. Ker-I Ko. 1991. Complexity Theory of Real Functions. Birkh\u00e4user, Boston, MA. 310 pages."},{"key":"e_1_2_1_15_1","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 -- 1416 . Leonid A. Levin. 1973. On the notion of a random sequence. Soviet Mathematics Doklady 14, 5 (1973), 1413--1416.","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_16_1","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 -- 35 . Leonid A. Levin. 1974. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii 10, 3 (1974), 30--35.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_17_1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"Li Ming","unstructured":"Ming Li and Paul Vit\u00e1nyi . 2008. An Introduction to Kolmogorov Complexity and Its Applications ( 3 rd ed.). Springer , New York, NY . 792 pages. Ming Li and Paul Vit\u00e1nyi. 2008. An Introduction to Kolmogorov Complexity and Its Applications (3rd ed.). Springer, New York, NY. 792 pages.","edition":"3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00187-1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/070684689"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200710060"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00343-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_62"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00035-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.03.006"},{"key":"e_1_2_1_25_1","first-page":"544","article-title":"On computable numbers, with an application to the Entscheidungsproblem. A correction","volume":"43","author":"Turing Alan M.","year":"1937","unstructured":"Alan M. Turing . 1937 . On computable numbers, with an application to the Entscheidungsproblem. A correction . Proceedings of the London Mathematical Society 43 , 2 (1937), 544 -- 546 . Alan M. Turing. 1937. On computable numbers, with an application to the Entscheidungsproblem. A correction. Proceedings of the London Mathematical Society 43, 2 (1937), 544--546.","journal-title":"Proceedings of the London Mathematical Society"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786566","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2786566","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:41Z","timestamp":1750223261000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2786566"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,9]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7,9]]}},"alternative-id":["10.1145\/2786566"],"URL":"https:\/\/doi.org\/10.1145\/2786566","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2015,7,9]]},"assertion":[{"value":"2014-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}