Back to Search
Start Over
The Communication Complexity of Correlation.
- Source :
-
IEEE Transactions on Information Theory . Jan2010, Vol. 56 Issue 1, p438-449. 12p. - Publication Year :
- 2010
-
Abstract
- Let X and y be finite nonempty sets and (X, Y) a pair of random variables taking values in X x Y. We consider communication protocols between two parties, ALICE and BOB, for generating X and Y. ALICE is provided an x ∈ X generated according to the distribution of X, and is required to send a message to BOB in order to enable him to generate y ∈ Y, whose distribution is the same as that of Y|X = x. Both parties have access to a shared random string generated in advance. Let T[X : Y] be the minimum (over all protocols) of the expected number of bits ALICE needs to transmit to achieve this. We show that I[X : Y] ≤ T[X : Y] ≤ I [X : Y] + 2 log2(I[X : Y] + 1) + 0(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bits ALICE must transmit for the worst case x ∈ X. We show that the communication required in this case is related to the capacity C(E) of the channel E, derived from (X, Y), that maps x ∈ X to the distribution of Y|X = x. We also show that the required communication T(E) satisfies C(E) ≤ T(E) ≤ C(E) + 2log2(C(E) + 1) + 0(1). Using the first result, we derive a direct-sum theorem in communication complexity that substantially improves the previous such result shown by Jain, Radhakrishnan, and Sen [In Proc. 30th International Colloquium of Automata, Languages and Programming (ICALP), ser. Lecture Notes in Computer Science, vol. 2719.2003, pp. 300-315]. These results are obtained by employing a rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 56
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 48051130
- Full Text :
- https://doi.org/10.1109/TIT.2009.2034824