Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence

Author Marius Zimand



PDF
Thumbnail PDF

File

LIPIcs.STACS.2009.1812.pdf
  • Filesize: 179 kB
  • 12 pages

Document Identifiers

Author Details

Marius Zimand

Cite As Get BibTex

Marius Zimand. Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 697-708, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1812

Abstract

An infinite binary sequence has randomness rate at least $\sigma$ if, for almost every $n$, the Kolmogorov complexity of its prefix of length $n$ is at least $\sigma n$. It is known that for every rational $\sigma \in (0,1)$, on one hand, there exists sequences with randomness rate $\sigma$ that can not be effectively transformed into a sequence with randomness rate higher than $\sigma$ and, on the other hand, any two independent sequences with randomness rate $\sigma$ can be transformed into a sequence with randomness rate higher than $\sigma$. We show that the latter result holds even if the two input sequences have linear dependency (which, informally speaking, means that all prefixes of length $n$ of the two sequences have in common a constant fraction of their information). The similar problem is studied for finite strings. It is shown that from any two strings with sufficiently large Kolmogorov complexity and sufficiently small dependence, one can effectively construct a string that is random even conditioned by any one of the input strings.

Subject Classification

Keywords
  • Algorithmic information theory
  • Computational complexity
  • Kolmogorov complexity
  • Randomness extractors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail