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

Revisions: 2

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