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

DOI10.4230/LIPIcs.STACS.2009.1812zbMath1236.68113arXiv0902.2141OpenAlexW1559443367MaRDI QIDQ5390019

Marius Zimand

Publication date: 24 April 2012

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

zbMATH Keywords

computational complexityalgorithmic information theoryKolmogorov complexityrandomness extractors

Mathematics Subject Classification ID

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

Related Items (6)

On Generating Independent Random Strings ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Algorithmically independent sequences ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences ⋮ On extracting space-bounded Kolmogorov complexity

This page was built for publication: Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence