Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Random noise increases Kolmogorov complexity and Hausdorff dimension   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$. This is always possible: Buhrman,
Fortnow, Newman and Vereshchagin (2005) showed that the increase can be at
least $\delta n$ for large $n$ (where $\delta$ is some positive number that
depends on $\alpha$ and the allowed fraction of changed bits).
  We consider a related question: what happens with the complexity of $x$ when
we randomly change a small fraction of the bits (changing each bit
independently with some probability $\tau$)? It turns out that a linear
increase in complexity happens with high probability, but this increase is
smaller than in the case of arbitrary change. We note that the amount of the
increase depends on $x$ (strings of the same complexity could behave
differently), and give an exact lower and upper bounds for this increase (with
$o(n)$ precision).
  The proof uses the combinatorial and probabilistic technique that goes back
to Ahlswede, G\'acs and K\"orner (1976). For the reader's convenience (and also
because we need a slightly stronger statement) we provide a simplified
exposition of this technique, so the paper is self-contained.

7
The categories of this paper are: hep-th
28
The categories of this paper are: alg-geom
4
The categories of this paper are: cond-mat
37
The categories of this paper are: supr-con
11
The categories of this paper are: hep-lat
20
The categories of this paper are: acc-phys
0
The categories of this paper are: hep-ph
10
The categories of this paper are: q-bio
33
The categories of this paper are: plasm-ph
19
The categories of this paper are: eess
6
The categories of this paper are: astro-ph
8
The categories of this paper are: hep-ex
30
The categories of this paper are: q-alg
24
The categories of this paper are: dg-ga
18
The categories of this paper are: econ
26
The categories of this paper are: bayes-an