  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 parties can establish via a probabilistic
protocol with interaction on a public channel, assuming that the parties hold
as their inputs x and y respectively. We determine the worst-case communication
complexity of this problem for the setting where the parties can use private
sources of random bits. We show that for some x, y the communication complexity
of the secret key agreement does not decrease even if the parties have to agree
on a secret key whose size is much smaller than the mutual information between
x and y. On the other hand, we discuss examples of x, y such that the
communication complexity of the protocol declines gradually with the size of
the derived secret key. The proof of the main result uses spectral properties
of appropriate graphs and the expander mixing lemma, as well as information
theoretic techniques.
