10.4230/LIPICS.STACS.2020.46
Bauwens, Bruno
Bruno
Bauwens
https://orcid.org/0000-0002-6138-0591
National Research University Higher School of Economics, Moscow, Russia
Information Distance Revisited
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
ConferencePaper
Kolmogorov complexity
algorithmic information distance
en
Christophe Paul
https://orcid.org/0000-0001-6519-975X
National Research University Higher School of Economics, Moscow, Russia
Markus Bläser
National Research University Higher School of Economics, Moscow, Russia
https://arxiv.org/abs/1807.11087
10.4230/LIPIcs.STACS.2020
978-3-95977-140-5
1868-8969
http://arxiv.org/abs/1807.11087
https://doi.org/10.1145/321892.321894
http://www.lirmm.fr/~ashen/kolmbook-eng.pdf
http://arxiv.org/abs/1410.7328
Creative Commons Attribution 3.0 Unported license
We consider the notion of information distance between two objects x and y introduced by Bennett, Gács, Li, Vitanyi, and Zurek [C. H. Bennett et al., 1998] as the minimal length of a program that computes x from y as well as computing y from x, and study different versions of this notion. In the above paper, it was shown that the prefix version of information distance equals max (K(x|y),K(y|x)) up to additive logarithmic terms. It was claimed by Mahmud [Mahmud, 2009] that this equality holds up to additive O(1)-precision. We show that this claim is false, but does hold if the distance is at least logarithmic. This implies that the original definition provides a metric on strings that are at superlogarithmically separated.
LIPIcs, Vol. 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 46:1-46:14