Generating Kolmogorov random strings from sources with limited independence

DOI10.1093/LOGCOM/EXR053MaRDI QIDQ2844006zbMATHOpenAlexFDO

Authors Marius Zimand

Publication date 27 August 2013

Published in Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exr053

zbMATH Keywords

computational complexityKolmogorov complexityrandomness extractorsalgorithmic information theory

Mathematics Subject Classification ID

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

Recommendations

• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• On generating independent random strings
• Impossibility of independence amplification in Kolmogorov complexity theory
• Counting dependent and independent strings
• On extracting space-bounded Kolmogorov complexity

Cited in

(8)

• What can be efficiently reduced to the Kolmogorov-random strings?
• An excursion to the Kolmogorov random strings
• On generating independent random strings
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Impossibility of independence amplification in Kolmogorov complexity theory
• Short lists with short programs in short time
• Counting dependent and independent strings
• Sets of \(K\)-independent strings

This page was built for publication: Generating Kolmogorov random strings from sources with limited independence

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