Posobin, Gleb ;
Shen, Alexander
Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension
Abstract
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 alpharandom 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].
BibTeX  Entry
@InProceedings{posobin_et_al:LIPIcs:2019:10296,
author = {Gleb Posobin and Alexander Shen},
title = {{Random Noise Increases Kolmogorov Complexity and Hausdorff Dimension}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {57:157:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10296},
doi = {10.4230/LIPIcs.STACS.2019.57},
annote = {Keywords: Kolmogorov complexity, effective Hausdorff dimension, random noise}
}
12.03.2019
Keywords: 

Kolmogorov complexity, effective Hausdorff dimension, random noise 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

12.03.2019 