Random noise increases Kolmogorov complexity and Hausdorff dimension

Gleb Posobin, Alexander Shen

Consider a binary string $x$ of length $n$ whose Kolmogorov complexity is $\alpha n$ for some $\alpha <1$. We want to increase the complexity of $x$ by changing a small fraction of bits in $x$…