The Communication Complexity of Correlation

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. Aliceand 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 coin tosses) is small for each D ϵ 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. [JRSb].

1 Introduction

Let and be finite non-empty sets, and let be a pair of (correlated) random variables taking values in . Consider the following communication problem between two parties, Alice and Bob. Alice is given a random input , sampled according to the distribution . (We use the same symbol to refer to a random variable and its distribution.) Alice needs to transmit a message to Bob so that Bob can generate a value , that is distributed according to the conditional distribution (i.e., the pair has joint distribution . How many bits must Alice send Bob in any protocol that accomplishes this? It follows from the data processing inequality in information theory that this minimum, which we shall call , is at least the mutual information between, and , that is,

$$I[X\ : \ Y]\ \triangleq\ H[X]+H[Y]-H[X, Y],$$ where denotes the Shannon entropy of the random variable . (This lower bound follows from the following sequence of inequalities: , where the last inequality is the data processing inequality (cf. [CT, Page 32, Theorem 2.8.1]) applied to the Markov chain .) We can also consider a slightly relaxed version of this problem which allows for some error. More formally, let denote the minimum expected number of bits Alice needs to send Bob so that the joint distribution generated by the protocol, which we call , to be -close in total variation distance¹

The total variation distance between two distribution and is defined as , which is also equal to where is the -norm

to the joint distribution .