Impossibility of independence amplification in Kolmogorov complexity theory

DOI10.1007/978-3-642-15155-2_61zbMATH Open1287.68085arXiv1006.0701OpenAlexW1866066107MaRDI QIDQ3586124FDOQ3586124

Authors: Marius Zimand 

Publication date: 3 September 2010

Published in: Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

Abstract: 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 $mdep(x,y)=maxC(x)-C(xmidy),C(y)-C(ymidx)$, 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 $$ for all $n$-bit strings $x$ and $y$ with $mdep(x,y)leqalpha(n)$, then $$.

Full work available at URL: https://arxiv.org/abs/1006.0701

Recommendations

• Generating Kolmogorov random strings from sources with limited independence
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Kolmogorov complexity in randomness extraction
• Kolmogorov complexity in randomness extraction
• On extracting space-bounded Kolmogorov complexity

zbMATH Keywords

Kolmogorov complexityrandomness extractionrandom stringsindependent strings

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (5)

• Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
• Generating Kolmogorov random strings from sources with limited independence
• On extracting space-bounded Kolmogorov complexity
• On the impossibility of amplifying the independence of random variables
• Stability of properties of Kolmogorov complexity under relativization

This page was built for publication: Impossibility of independence amplification in Kolmogorov complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586124)