21 citations · 60 across the 30 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.IT2020
Inequalities for space-bounded Kolmogorov complexity
Bruno Bauwens, Peter Gács, Andrei Romashchenko +1
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples o…
cs.IT2020
Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory
Emirhan Gürpınar, Andrei Romashchenko
It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two part…