Impossibility of independence amplification in Kolmogorov complexity theory

DOI10.1007/978-3-642-15155-2_61MaRDI QIDQ3586124zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 3 September 2010

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

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

zbMATH Keywords

Kolmogorov complexityrandomness extractionrandom stringsindependent strings

Mathematics Subject Classification ID

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

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 $$.

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

Cited in

(4)

• On extracting space-bounded Kolmogorov complexity
• Generating Kolmogorov random strings from sources with limited independence
• Stability of properties of Kolmogorov complexity under relativization
• On the impossibility of amplifying the independence of random variables

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)