The Communication Complexity of Correlation

values in the set {0,1}^n. Let D be the marginal distribution of
X, and D_x the conditional distribution of Y given X=x. We
consider the following communication problem between two parties,
Alice and Bob, both of whom know the joint distribution (X,Y).
Alice will be given a random input x distributed according to D.
She needs to transmit a message to Bob so Bob can generate a value
in {0,1}^n with distribution D_x. For example, Alice can send x
across, and then Bob can pick a random value from the distribution
D_x. This protocol, however, can be wasteful. For example, if X
and Y are independent, Bob could have generated his value without
any help from Alice. Let C(X:Y) be the minimum expected number of
bits that Alice must transmit. We show that if Alice and Bob share
a random string (independent of Alice's input), then

I[X:Y] <= C(X:Y) <= I[X:Y] + O(log I[X:Y]),

where I[X:Y] = H[X] + H[Y] - H[XY] is the mutual information
between the random variables X and Y.

Before this work, a limit version of this result was known. Our
results are for the one-shot case, which imply the limit versions.
An important application of our result is improved direct sum
result in communication complexity, for which the limit versions
do not seem to help.

An essential ingredient in our proofs is a rejection sampling
procedure that relates the relative entropy between two
distributions to the communication complexity of generating one
distribution from the other.

[Joint Work with Rahul Jain, David McAllester and Jaikumar Radhakrishnan]