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 is an element of 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 is an element of Y, whose distribution is the same as that of Y vertical bar(X=x). Both parties have access to a shared random string generated in advance. Let T[X : T] 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 log(2)(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 is an element of 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 is an element of X to the distribution of Y vertical bar(X=x). We also show that the required communication T(E) satisfies C(E) <= T(E) <= C(E) + 2 log(2)(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.