Common information was introduced by Wyner as a measure of dependence of two
random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such
as communication ...
more >>>
We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings
$x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that
two parties, one having $x$ and the complexity profile of the pair and the ...
more >>>
