research
∙
04/10/2023
The Kraft–Barmpalias–Lewis-Pye lemma revisited
This note provides a simplified exposition of the proof of hierarchical ...
share
research
∙
09/15/2022
Inequalities for entropies and dimensions
We show that linear inequalities for entropies have a natural geometric ...
research
∙
03/28/2022
27 Open Problems in Kolmogorov Complexity
The paper proposes open problems in classical Kolmogorov complexity. Eac...
research
∙
11/01/2021
Individual codewords
Algorithmic information theory translates statements about classes of ob...
research
∙
10/31/2021
Gács-Kučera's Theorem Revisited by Levin
Leonid Levin (arxiv.org/abs/cs/0503039v14, p.7) published a new (and ver...
research
∙
10/20/2020
Inequalities for space-bounded Kolmogorov complexity
There is a parallelism between Shannon information theory and algorithmi...
research
∙
04/06/2020
Complexity of majorants
The minimal Kolmogorov complexity of a total computable function that ex...
research
∙
11/15/2018
Axiomatic approach to the theory of algorithms and relativized computability
It is well known that many theorems in recursion theory can be "relativi...
research
∙
08/14/2018
Random noise increases Kolmogorov complexity and Hausdorff dimension
Consider a binary string x of length n whose Kolmogorov complexity is α ...
research
∙
07/29/2018
Information Distance Revisited
We consider the notion of information distance between two objects x and...
research
∙
08/27/2017