Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-085 | 28th November 2003 00:00

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


Authors: Ke Yang
Publication: 8th December 2003 20:38
Downloads: 3105


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
non-interactively, i.e., they wish to each apply a function to their
strings, and output one random bit, denoted by $X$ and $Y$, such that
$\prob[X=Y]$ can be made as close to 1 as possible. The problem is,
for what noise model can they succeed? This problem is related to
various topics in computer science, including information
reconciliation and random beacons. In fact, if NICD is indeed possible
for some general class of noise models, then some of these topics
would, in some sense, become straightforward corollaries.

We prove two negative results on NICD for various noise models.
We prove that for these models, it is impossible to distill the
correlation to be arbitrarily close to 1. We also give an example
where Alice and Bob can increase their correlation with one bit of
communication (in this case they need to each output two bits). This
example, which may be of its own interest, demonstrates that even the
smallest amount of communication is provably more powerful than no

An extended abstract of this paper is to appear in the Latin American
Theoretical INformatics (LATIN 2004), Buenos Aires, Argentina, 2004.

ISSN 1433-8092 | Imprint