Inequalities for Shannon entropy and Kolmogorov complexity

DOI10.1006/jcss.1999.1677zbMath0988.94016OpenAlexW2132219316WikidataQ57349851 ScholiaQ57349851MaRDI QIDQ1567410

Alexander Shen, Andrei Romashchenko, Daniel Hammer, Nikolai K. Vereshchagin

Publication date: 10 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1999.1677

zbMATH Keywords

Kolmogorov complexitylinear inequalitiesShannon entropyIngleton's inequality

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Measures of information, entropy (94A17)

Related Items

Inequalities for space-bounded Kolmogorov complexity, Improving the linear programming technique in the search for lower bounds in secret sharing, Clustering with respect to the information distance, Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem, New inequalities for subspace arrangements, Stability of properties of Kolmogorov complexity under relativization, Inequalities for entropies and dimensions, Coordination and discoordination in linear algebra, linear information theory, and coded caching, Ideal multipartite secret sharing schemes, Is there a universal image generator?, SECOND QUANTIZED KOLMOGOROV COMPLEXITY, Normalized information-based divergences, Recent progresses in characterising information inequalities, On a connection between information and group lattices, On group-characterizability of homomorphic secret sharing schemes, Ideal Secret Sharing Schemes for Useful Multipartite Access Structures, Kolmogorov Complexity as a Language, Analysing causal structures with entropy, LOSSLESS QUANTUM DATA COMPRESSION AND QUANTUM KOLMOGOROV COMPLEXITY, Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\), Combinatorial interpretation of Kolmogorov complexity, Algorithmic Statistics Revisited, Complexity and uncertainty analysis of financial stock markets based on entropy of scale exponential spectrum, On abelian and homomorphic secret sharing schemes, Mutual Dimension

Cites Work

• A strange application of Kolmogorov complexity
• Relations between varieties of kolmogorov complexities
• Logical basis for information theory and probability theory
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item