Variations on Muchnik's conditional complexity theorem
From MaRDI portal
Publication:639853
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
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