Impossibility of independence amplification in Kolmogorov complexity theory

Details Impossibility of independence amplification in Kolmogorov complexity theory Impossibility of independence amplification in Kolmogorov complexity theory

2010-06-03

arxiv.org/abs/1006.0701v1

Computer Science

Computational Complexity

Scientific paper

The paper studies randomness extraction from sources with bounded independence and the issue of independence amplification of sources, using the framework of Kolmogorov complexity. The dependency of strings $x$ and $y$ is ${\rm dep}(x,y) = \max\{C(x) - C(x \mid y), C(y) - C(y\mid x)\}$, where $C(\cdot)$ denotes the Kolmogorov complexity. It is shown that there exists a computable Kolmogorov extractor $f$ such that, for any two $n$-bit strings with complexity $s(n)$ and dependency $\alpha(n)$, it outputs a string of length $s(n)$ with complexity $s(n)- \alpha(n)$ conditioned by any one of the input strings. It is proven that the above are the optimal parameters a Kolmogorov extractor can achieve. It is shown that independence amplification cannot be effectively realized. Specifically, if (after excluding a trivial case) there exist computable functions $f_1$ and $f_2$ such that ${\rm dep}(f_1(x,y), f_2(x,y)) \leq \beta(n)$ for all $n$-bit strings $x$ and $y$ with ${\rm dep}(x,y) \leq \alpha(n)$, then $\beta(n) \geq \alpha(n) - O(\log n)$.

Affiliated with

Also associated with

No associations

Rating

Impossibility of independence amplification in Kolmogorov complexity theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Impossibility of independence amplification in Kolmogorov complexity theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Impossibility of independence amplification in Kolmogorov complexity theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-514212