期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the problem of non-interactive correlation distillation (NICD). Suppose Alice and Bob each has a string, denoted by A = a 0 a 1 a n − 1 and B = b 0 b 1 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 communication. An extended abstract of this paper is to appear in the Latin American Theoretical INformatics (LATIN 2004), Buenos Aires, Argentina, 2004.
关键词：Communication complexity , correlation distillation , Fourier analysis , information reconciliation , random beacon
