Kolmogorov Complexity with Error

DOI10.1007/11672142_10MaRDI QIDQ5449793zbMATH OpenOpenAlexFDO

Authors Troy Lee, Lance Fortnow, Nikolai K. Vereshchagin

Publication date 19 March 2008

Published in STACS 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11672142_10

Mathematics Subject Classification ID

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

Recommendations

• Information distance and conditional complexities
• Mathematical Foundations of Computer Science 2004
• On approximate uncomputability of the Kolmogorov complexity function
• Randomized communication complexity of approximating Kolmogorov complexity
• Information distance

Cited in

(6)

• Randomness, computation and mathematics
• A safe approximation for Kolmogorov complexity
• Dimensions of Points in Self-similar Fractals
• On approximate uncomputability of the Kolmogorov complexity function
• Randomized communication complexity of approximating Kolmogorov complexity
• Kolmogorov complexity and the asymptotic bound for error-correcting codes

This page was built for publication: Kolmogorov Complexity with Error

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