Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with common information:
TR00-015 | 16th February 2000
Andrej Muchnik, Alexej Semenov

Multi-conditional Descriptions and Codes in Kolmogorov Complexity

TR13-158 | 18th November 2013
Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Information-theoretic approximations of the nonnegative rank

Revisions: 3

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 >>>

TR18-043 | 22nd February 2018
Andrei Romashchenko, Marius Zimand

An operational characterization of mutual information in algorithmic information theory

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 >>>

ISSN 1433-8092 | Imprint