Combinatorial interpretation of Kolmogorov complexity

DOI10.1016/S0304-3975(01)00034-2MaRDI QIDQ5958285zbMATH OpenWikidataFDO

Authors Andrei Romashchenko, A. Shen, Nikolai K. Vereshchagin

Publication date 3 March 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00034-2

zbMATH Keywords

combinatoricsinequalitiesKolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• Inequalities for Shannon entropy and Kolmogorov complexity
• scientific article; zbMATH DE number 107774
• Kolmogorov complexity arguments in combinatorics
• Shannon Entropy vs. Kolmogorov Complexity
• A strange application of Kolmogorov complexity

Cites work

• A strange application of Kolmogorov complexity
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• Inequalities for Shannon entropy and Kolmogorov complexity
• Relations between varieties of kolmogorov complexities

Cited in

(15)

• The proof of Levin's conjecture
• Kolmogorov complexity arguments in combinatorics
• Inequalities for Shannon entropy and Kolmogorov complexity
• Algorithmic statistics revisited
• Randomized polynomial time protocol for combinatorial Slepian-Wolf problem
• Kolmogorov complexity as a language
• On the complexity of some geometrical objects
• On the Combinatorial Representation of Information
• Relations between varieties of kolmogorov complexities
• Inequalities for space-bounded Kolmogorov complexity
• Computing from projections of random points
• scientific article; zbMATH DE number 3340909 (Why is no real title available?)
• Stability of properties of Kolmogorov complexity under relativization
• Chair of Mathematical Logic and Theory of Algorithms
• Partitioning multi-dimensional sets in a small number of ``uniform parts

This page was built for publication: Combinatorial interpretation of Kolmogorov complexity

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