The Communication Complexity of Correlation
Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan · IEEE Transactions on Information Theory · 2007
LetXandYbe finite nonempty sets and(X,Y) a pair of random variables taking values inX?Y. We consider communication protocols between two parties,AliceandBob, for generatingXandY.Aliceis provided anx?Xgenerated according to the distribution ofX, and is required to send a message toBobin order to enable him to generatey?Y, whose distribution is the same as that ofY|X=x. Both parties have access to a shared random string generated in advance. LetT[X:Y] be the minimum (over all protocols) of the expected number of bitsAliceneeds to transmit to achieve this. We show that I[X:Y] ? T[X:Y] ? I [X:Y] + 2 log2(I[X:Y]+ O(1). We also consider the worst case communication required for this problem, where we seek to minimize the average number of bitsAlicemust transmit for the worst casex?X. We show that the communication required in this case is related to the capacityC(E) of the channelE, derived from(X,Y) , that mapsx?Xto the distribution ofY|X=x. We also show that the required communicationT(E) satisfiesC(E) ?T(E) ?C(E) + 2 log2(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.