Document

**Published in:** LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Consider a bit string x of length n and Kolmogorov complexity alpha n (for some alpha<1). It is always possible to increase the complexity of x by changing a small fraction of bits in x [Harry Buhrman et al., 2005]. What happens with the complexity of x when we randomly change each bit independently with some probability tau? We prove that a linear increase in complexity happens with high probability, but this increase is smaller than in the case of arbitrary change considered in [Harry Buhrman et al., 2005]. The amount of the increase depends on x (strings of the same complexity could behave differently). We give exact lower and upper bounds for this increase (with o(n) precision).
The same technique is used to prove the results about the (effective Hausdorff) dimension of infinite sequences. We show that random change increases the dimension with probability 1, and provide an optimal lower bound for the dimension of the changed sequence. We also improve a result from [Noam Greenberg et al., 2018] and show that for every sequence omega of dimension alpha there exists a strongly alpha-random sequence omega' such that the Besicovitch distance between omega and omega' is 0.
The proofs use the combinatorial and probabilistic reformulations of complexity statements and the technique that goes back to Ahlswede, Gács and Körner [Ahlswede et al., 1976].

Gleb Posobin and Alexander Shen. Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{posobin_et_al:LIPIcs.STACS.2019.57, author = {Posobin, Gleb and Shen, Alexander}, title = {{Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {57:1--57:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.57}, URN = {urn:nbn:de:0030-drops-102969}, doi = {10.4230/LIPIcs.STACS.2019.57}, annote = {Keywords: Kolmogorov complexity, effective Hausdorff dimension, random noise} }

Document

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

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].

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.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} }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

The main goal of this paper is to put some known results in a
common perspective and to simplify their proofs.
We start with a simple proof of a result from (Vereshchagin, 2002)
saying that $limsup_{nKS(x|n)$ (here $KS(x|n)$ is conditional
(plain) Kolmogorov complexity of $x$ when $n$ is known) equals
$KS^{mathbf{0'(x)$, the plain Kolmogorov complexity with
$mathbf{0'$-oracle.
Then we use the same argument to prove similar results for prefix
complexity (and also improve results of (Muchnik, 1987) about limit
frequencies), a priori probability on binary tree and measure of
effectively open sets. As a by-product, we get a criterion of
$mathbf{0'$ Martin-L"of randomness (called also $2$-randomness)
proved in (Miller, 2004): a sequence $omega$ is $2$-random if and
only if there exists $c$ such that any prefix $x$ of $omega$ is a
prefix of some string $y$ such that $KS(y)ge |y|-c$. (In the
1960ies this property was suggested in (Kolmogorov, 1968) as one of
possible randomness definitions; its equivalence to $2$-randomness
was shown in (Miller, 2004) while proving another $2$-randomness
criterion (see also (Nies et al. 2005)): $omega$ is $2$-random if
and only if $KS(x)ge |x|-c$ for some $c$ and infinitely many
prefixes $x$ of $omega$.
Finally, we show that the low-basis theorem can be used to get
alternative proofs for these results and to improve the result
about effectively open sets; this stronger version implies the
$2$-randomness criterion mentioned in the previous sentence.

Laurent Bienvenu, Andrej Muchnik, Alexander Shen, and Nikolay Veraschagin. Limit complexities revisited. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2008.1335, author = {Bienvenu, Laurent and Muchnik, Andrej and Shen, Alexander and Veraschagin, Nikolay}, title = {{Limit complexities revisited}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {73--84}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1335}, URN = {urn:nbn:de:0030-drops-13350}, doi = {10.4230/LIPIcs.STACS.2008.1335}, annote = {Keywords: Kolmogorov complexity, limit complexities, limit frequencies, 2-randomness, low basis} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Original proof of Muchnik's theorem on conditional descriptions can be modified and split into two parts:
1) we construct a graph that allows large online matchings (main part)
2) we use this graph to prove the theorem
The question about online matching could be interesting in itself.

Alexander Shen. Combinatorial proof of Muchnik's theorem. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{shen:DagSemProc.06051.5, author = {Shen, Alexander}, title = {{Combinatorial proof of Muchnik's theorem}}, booktitle = {Kolmogorov Complexity and Applications}, pages = {1--5}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6051}, editor = {Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.5}, URN = {urn:nbn:de:0030-drops-6258}, doi = {10.4230/DagSemProc.06051.5}, annote = {Keywords: Matching conditional descriptions Kolmogorov complexity} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 6051, Kolmogorov Complexity and Applications (2006)

Multisource information theory is well known in Shannon setting. It studies the possibilities of information transfer through a network with limited capacities. Similar questions could be studied for algorithmic information theory and provide a framework for several known results and interesting questions.

Alexander Shen. Multisource Algorithmic Information Theory. In Kolmogorov Complexity and Applications. Dagstuhl Seminar Proceedings, Volume 6051, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{shen:DagSemProc.06051.9, author = {Shen, Alexander}, title = {{Multisource Algorithmic Information Theory}}, booktitle = {Kolmogorov Complexity and Applications}, pages = {1--12}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6051}, editor = {Marcus Hutter and Wolfgang Merkle and Paul M.B. Vitanyi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06051.9}, URN = {urn:nbn:de:0030-drops-6267}, doi = {10.4230/DagSemProc.06051.9}, annote = {Keywords: Kolmogorov complexity multisource information theory} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Bruno Durand, Leonid A. Levin, Wolfgang Merkle, Alexander Shen, and Paul M. B. Vitanyi. Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181). Dagstuhl Seminar Report 377, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{durand_et_al:DagSemRep.377, author = {Durand, Bruno and Levin, Leonid A. and Merkle, Wolfgang and Shen, Alexander and Vitanyi, Paul M. B.}, title = {{Centennial Seminar on Kolmogorov Complexity and Applications (Dagstuhl Seminar 03181)}}, pages = {1--6}, ISSN = {1619-0203}, year = {2003}, type = {Dagstuhl Seminar Report}, number = {377}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.377}, URN = {urn:nbn:de:0030-drops-152578}, doi = {10.4230/DagSemRep.377}, }