Inequalities for space-bounded Kolmogorov complexity
From MaRDI portal
Publication:5061387
DOI10.3233/COM-210374zbMath1506.68041arXiv2010.10221OpenAlexW3093851029MaRDI QIDQ5061387
Peter Gács, Alexander Shen, Andrei Romashchenko, Bruno Bauwens
Publication date: 12 January 2023
Published in: Computability (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.10221
Cites Work
- Unnamed Item
- Unnamed Item
- Halting space-bounded computations
- A combinatorial approach to information inequalities
- Inequalities for Shannon entropy and Kolmogorov complexity
- Symmetry of information and one-way functions
- Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
- Algorithmic Statistics Revisited
- Algorithmic Statistics: Forty Years Later
- On a relation between information inequalities and group theory
- On characterization of entropy function via information inequalities
- Logical basis for information theory and probability theory
- Combinatorial interpretation of Kolmogorov complexity
This page was built for publication: Inequalities for space-bounded Kolmogorov complexity