Combinatorial interpretation of Kolmogorov complexity

DOI10.1016/S0304-3975(01)00034-2zbMath0992.68081WikidataQ57349804 ScholiaQ57349804MaRDI QIDQ5958285

Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin

Publication date: 3 March 2002

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

zbMATH Keywords

combinatoricsinequalitiesKolmogorov complexity

Mathematics Subject Classification ID

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

Related Items (8)

Inequalities for space-bounded Kolmogorov complexity ⋮ On the Complexity of Some Geometrical Objects ⋮ Partitioning multi-dimensional sets in a small number of ``uniform parts ⋮ Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem ⋮ Stability of properties of Kolmogorov complexity under relativization ⋮ Computing from projections of random points ⋮ Kolmogorov Complexity as a Language ⋮ Algorithmic Statistics Revisited

Cites Work

• Unnamed Item
• Unnamed Item
• A strange application of Kolmogorov complexity
• Inequalities for Shannon entropy and Kolmogorov complexity
• Relations between varieties of kolmogorov complexities

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