Speaker: |
Madhu Sudan (Microsoft Research, New England) |

Organiser: |
Prahladh Harsha |

Date: |
Monday, 12 Jan 2015, 14:30 to 15:30 |

Venue: |
AG-80 |

(Scan to add to calendar)

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. The talk will assume no background in communication complexity and/or influence of variables.

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