Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with information reconciliation:
TR03-085 | 28th November 2003
Ke Yang

On the (Im)possibility of Non-interactive Correlation Distillation

We study the problem of non-interactive correlation distillation
(NICD). Suppose Alice and Bob each has a string, denoted by
$A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$,
respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is
independently drawn from a distribution $\noise$, known as the ``noise
mode''. Alice and Bob wish to ``distill'' the correlation
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