The Communication Complexity of Correlation.

Let X and y be finite nonempty sets and (X, Y) a pair of random variables taking values in X 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) + 0(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) + 0(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. [ABSTRACT FROM AUTHOR]