Variations on Muchnik's conditional complexity theorem

DOI10.1007/s00224-011-9321-zzbMath1235.68089arXiv0904.3116OpenAlexW2571410429WikidataQ57349583 ScholiaQ57349583MaRDI QIDQ639853

Alexander Shen, Daniil Musatov, Andrei Romashchenko

Publication date: 11 October 2011

Published in: Theory of Computing Systems, Computer Science - Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

Kolmogorov complexityextractorson-line matching

Mathematics Subject Classification ID

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

Related Items (5)

Variations on Muchnik's conditional complexity theorem ⋮ Short lists for shortest descriptions in short time ⋮ Short lists with short programs in short time ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ On extracting space-bounded Kolmogorov complexity

Cites Work

• Unnamed Item
• Variations on Muchnik's conditional complexity theorem
• Language compression and pseudorandom generators
• Hardness vs randomness
• Decoding of Reed Solomon codes beyond the error-correction bound
• Resource-Bounded Kolmogorov Complexity Revisited
• Construction of extractors using pseudo-random generators (extended abstract)
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Extracting Randomness via Repeated Condensing
• Noiseless coding of correlated information sources
• Conditional complexity and codes

This page was built for publication: Variations on Muchnik's conditional complexity theorem