The communication complexity of correlation

Harsha, P. ; Jain, R. ; McAllester, D. ; Radhakrishnan, J. (2007) The communication complexity of correlation Proceedings - IEEE Conference on Computational Complexity . pp. 10-23. ISSN 1093-0159

Full text not available from this repository.

Official URL:

Related URL:


We examine the communication required for generating random variables remotely. One party Alice is given a distribution D, and she has to send a message to Bob, who is then required to generate a value with distribution exactly D. Alice and Bob are allowed to share random bits generated without the knowledge of D. There are two settings based on how the distribution D provided to Alice is chosen. If D is itself chosen randomly from some set (the set and distribution are known in advance) and we wish to minimize the expected communication in order for Alice to generate a value y, with distribution D, then we characterize the communication required in terms of the mutual information between the input to Alice and the output Bob is required to generate. If D is chosen from a set of distributions D, and we wish to devise a protocol so that the expected communication (the randomness comes from the shared random string and Alice's coin tosses) is small for each D isin D, then we characterize the communication required in this case in terms of the channel capacity associated with the set D. Our proofs are based on an improved rejection sampling procedure that relates the relative entropy between two distributions to the communication complexity of generating one distribution from the other. As an application of these results, we derive a direct sum theorem in communication complexity that substantially improves the previous such result shown by Jain et al. (2003).

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:89498
Deposited On:27 Apr 2012 13:40
Last Modified:27 Apr 2012 13:40

Repository Staff Only: item control page