Title: Communication Amid Uncertainty

Speaker: Madhu Sudan (Harvard)

Abstract: I will talk about a sequence of works where we investigate basic questions in communication where unreliability can be attributed, not to the channel of communication, but to the lack of perfect synchronization between the communicating players. Topics that will be covered include (some subset of):

1) (One-shot) Compression where sender and receiver of information do not agree on the distribution from which the message is sampled. Can we compress information down to the entropy?
2) Communication complexity when Alice and Bob don't have perfectly shared randomness: Is having shared correlation as good as having perfectly shared randomness?
3) Communication complexity when Alice and Bob don't agree on the function being computed. Can one salvage low-communication protocols with such uncertainty?
4) Communication of proofs (as in our conference/journal papers) where prover and verifier don't agree on what is basic math.

In most cases we have only partial results, and I will describe what we know and the many open questions.

Based on many joint works.