2 Search Results for "Andreev, Mikhail"

Document
DOI: 10.4230/LIPIcs.STACS.2020.46
Information Distance Revisited

Authors: Bruno Bauwens

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
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.
Cite as

Bruno Bauwens. Information Distance Revisited. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bauwens:LIPIcs.STACS.2020.46,
  author =	{Bauwens, Bruno},
  title =	{{Information Distance Revisited}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.46},
  URN =		{urn:nbn:de:0030-drops-119071},
  doi =		{10.4230/LIPIcs.STACS.2020.46},
  annote =	{Keywords: Kolmogorov complexity, algorithmic information distance}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.2
Plain Stopping Time and Conditional Complexities Revisited

Authors: Mikhail Andreev, Gleb Posobin, and Alexander Shen

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper we analyze the notion of "stopping time complexity", the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by Vovk and Pavlovic [Vovk and Pavlovic, 2016]. It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) the minimal plain complexity of a Turing machine that stops after reading x on a one-directional input tape; (b) the minimal plain complexity of an algorithm that enumerates a prefix-free set containing x; (c) the conditional complexity C(x|x*) where x in the condition is understood as a prefix of an infinite binary sequence while the first x is understood as a terminated binary string; (d) as a minimal upper semicomputable function K such that each binary sequence has at most 2^n prefixes z such that K(z)<n; (e) as maxC^X(x) where C^X(z) is plain Kolmogorov complexity of z relative to oracle X and the maximum is taken over all extensions X of x. We also show that some of these equivalent definitions become non-equivalent in the more general setting where the condition y and the object x may differ, and answer an open question from Chernov, Hutter and Schmidhuber [Alexey V. Chernov et al., 2007].
Cite as

Mikhail Andreev, Gleb Posobin, and Alexander Shen. Plain Stopping Time and Conditional Complexities Revisited. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:LIPIcs.MFCS.2018.2,
  author =	{Andreev, Mikhail and Posobin, Gleb and Shen, Alexander},
  title =	{{Plain Stopping Time and Conditional Complexities Revisited}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.2},
  URN =		{urn:nbn:de:0030-drops-95842},
  doi =		{10.4230/LIPIcs.MFCS.2018.2},
  annote =	{Keywords: Kolmogorov complexity, stopping time complexity, structured conditional complexity, algorithmic information theory}
}
  • Refine by Author
  • 1 Andreev, Mikhail
  • 1 Bauwens, Bruno
  • 1 Posobin, Gleb
  • 1 Shen, Alexander

  • Refine by Classification
  • 1 Mathematics of computing → Information theory
  • 1 Theory of computation

  • Refine by Keyword
  • 2 Kolmogorov complexity
  • 1 algorithmic information distance
  • 1 algorithmic information theory
  • 1 stopping time complexity
  • 1 structured conditional complexity

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact