Please use this identifier to cite or link to this item:
https://doi.org/10.1109/TIT.2009.2034824
DC Field | Value | |
---|---|---|
dc.title | The Communication complexity of correlation | |
dc.contributor.author | Harsha, P. | |
dc.contributor.author | Jain, R. | |
dc.contributor.author | McAllester, D. | |
dc.contributor.author | Radhakrishnan, J. | |
dc.date.accessioned | 2013-07-04T07:32:35Z | |
dc.date.available | 2013-07-04T07:32:35Z | |
dc.date.issued | 2010 | |
dc.identifier.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 | |
dc.identifier.issn | 00189448 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/39040 | |
dc.description.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. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1109/TIT.2009.2034824 | |
dc.source | Scopus | |
dc.subject | Communication complexity | |
dc.subject | Direct sum | |
dc.subject | Mutual information | |
dc.subject | Rejection sampling | |
dc.subject | Relative entropy | |
dc.type | Article | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1109/TIT.2009.2034824 | |
dc.description.sourcetitle | IEEE Transactions on Information Theory | |
dc.description.volume | 56 | |
dc.description.issue | 1 | |
dc.description.page | 438-449 | |
dc.description.coden | IETTA | |
dc.identifier.isiut | 000273134100031 | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.