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

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.
Keywords :
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.697-708, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Domaine :

Littérature citée [7 références]

https://hal.inria.fr/inria-00360150
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 14:38:48
Dernière modification le : vendredi 13 février 2009 - 10:08:51
Document(s) archivé(s) le : mardi 8 juin 2010 - 18:52:21

Fichiers

zimand_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

• HAL Id : inria-00360150, version 1
• ARXIV : 0902.2141

Citation

Marius Zimand. Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science - STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.697-708, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360150〉

Métriques

Consultations de la notice

68

Téléchargements de fichiers