Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with mutual information:
TR00-035 | 6th June 2000
Nikolay Vereshchagin, Mikhail V. Vyugin

Independent minimum length programs to translate between given strings

A string $p$ is called a program to compute $y$ given $x$
if $U(p,x)=y$, where $U$ denotes universal programming language.
Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$
is defined as minimum length of
a program to compute $y$ given $x$.
Let $K(x)$ denote $K(x|\text{empty string})$
(Kolmogorov complexity of $x$) ... more >>>

TR06-151 | 10th December 2006
Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

The communication complexity of correlation

We examine the communication required for generating random variables
remotely. One party Alice will be given a distribution D, and she
has to send a message to Bob, who is then required to generate a
value with distribution exactly D. Alice and Bob are allowed
to share random bits generated ... more >>>

TR11-164 | 9th December 2011
Mark Braverman, Omri Weinstein

A discrepancy lower bound for information complexity

This paper provides the first general technique for proving information lower bounds on two-party
unbounded-rounds communication problems. We show that the discrepancy lower bound, which
applies to randomized communication complexity, also applies to information complexity. More
precisely, if the discrepancy of a two-party function $f$ with respect ... more >>>

TR14-133 | 15th October 2014
Adam Case, Jack H. Lutz

Mutual Dimension

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... 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