Communication with Imperfectly Shared Randomness

Madhu Sudan (MSR)

In the 1980's Yao introduced the model of communication complexity where Alice, who knows x in {0,1}^n, and Bob, who knows y in {0,1}^n, wish to communicate with each other, exchanging fewest possible number of bits, to determine some function f(x,y). For many natural functions f this communication complexity is much smaller than the trivial n bits suggesting that communication with a goal in mind may be much less expensive than otherwise. This message gets amplified even more if Alice and Bob share some random string r chosen independently of x and y: in this setting even more functions f can be determined quickly (with high probability).

In this talk I will introduce a relaxation of this model where Alice and Bob do not share the random string perfectly, but rather Alice knows r and Bob knows some string s that is correlated with r. I will describe some recent results showing that any communication protocol with k bits of communication between Alice and Bob with perfect sharing of randomness, continues to have a moderately low-complexity, 2^k bit, protocol with shared correlation. Furthermore, I will show that this result is tight in that there exist problems where this exponential jump is necessary. The technical core of these results rely on the understanding of the influence of variables in the analysis of Boolean functions and recently developed probabilistic tools such as the ``invariance principle'' of Mossel, O'Donnell and Oleszkiewicz.  One hope of the talk is to explain what these tools are, and why computer scientists find them useful.

Based on joint work with Clément Canonne (Columbia), Venkatesan Guruswami (CMU) and Raghu Meka ().