Generating Kolmogorov random strings from sources with limited independence

DOI10.1093/LOGCOM/EXR053zbMATH Open1271.68114OpenAlexW2090841310MaRDI QIDQ2844006FDOQ2844006

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

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

zbMATH Keywords

computational complexityKolmogorov complexityrandomness extractorsalgorithmic information theory

Mathematics Subject Classification ID

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

Cited In (8)

• An excursion to the Kolmogorov random strings
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Impossibility of independence amplification in Kolmogorov complexity theory
• What can be efficiently reduced to the Kolmogorov-random strings?
• Counting dependent and independent strings
• On generating independent random strings
• Short lists with short programs in short time
• 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)