Please use this identifier to cite or link to this item:
|Title:||The Communication complexity of correlation|
|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. https://doi.org/10.1109/TIT.2009.2034824|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Nov 19, 2018
WEB OF SCIENCETM
checked on Nov 19, 2018
checked on Oct 13, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.