Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension


Consider a bit string x of length n and Kolmogorov complexity αn (for some α < 1). It is always possible to increase the complexity of x by changing a small fraction of bits in x [2]. What happens with the complexity of x when we randomly change each bit independently with some probability τ ? 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 [2]. 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 [5] and show that for every sequence ω of dimension α there exists a strongly α-random sequence ω such that the Besicovitch distance between ω and ω 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 [1].
Fichier principal
Vignette du fichier
LIPIcs-STACS-2019-57.pdf (504.01 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-02084843 , version 1 (29-03-2019)



Gleb Posobin, Alexander Shen. Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension. STACS 2019 - 36th International Symposium on Theoretical Aspects of Computer Science, Mar 2019, Berlin, Germany. pp.57:1--57:14, ⟨10.4230/LIPIcs.STACS.2019.57⟩. ⟨lirmm-02084843⟩
72 View
73 Download



Gmail Mastodon Facebook X LinkedIn More