Please use this identifier to cite or link to this item:
Title: The Communication complexity of correlation
Authors: Harsha, P.
Jain, R. 
McAllester, D.
Radhakrishnan, J.
Keywords: Communication complexity
Direct sum
Mutual information
Rejection sampling
Relative entropy
Issue Date: 2010
Citation: Harsha, P., Jain, R., McAllester, D., Radhakrishnan, J. (2010). The Communication complexity of correlation. IEEE Transactions on Information Theory 56 (1) : 438-449. ScholarBank@NUS Repository.
Abstract: Let X and Y be finite nonempty sets and (X, Y) a pair of random variables taking values in 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) + O(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) + O(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. © 2009 IEEE.
Source Title: IEEE Transactions on Information Theory
ISSN: 00189448
DOI: 10.1109/TIT.2009.2034824
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on May 18, 2018


checked on Mar 21, 2018

Page view(s)

checked on Mar 11, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.