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…