Madhu Sudan: Communication Amid Uncertainty

Abstract:  Computers and humans communicate in order to gain information about the state of the world around them, and to be able to determine how to act in the future.  Effective communication relies on large shared context between the communicating parties: Such shared context tells the communicating agents how to compress information, how to overcome noise in communication channels and how to interpret the messages so as to be able to act based on them. To this date however almost all designed systems assume this context is shared perfectly by the communicating agents --- and any violation leads to a breakdown in communication (devices don't print, emails can't be opened etc.) Is it possible to design reliable communication protocols that don't assume such perfect synchronization between sender and receiver?

In this talk we will describe some of our attempts to build theoretical models of communication when communicating players are uncertain about different aspects of the context. Depending on the time available we will show how
  1) Data can be compressed even when sender and receiver are not in agreement on the prior from which the data is sampled.
  2) Probabilistic communication strategies can be implemented even when sender and receiver don't share the randomness perfectly.
  3) Somewhat unfocussed communication can be almost as effective as communication with a sharp focus.

Based on joint works with Brendan Juba, Oded Goldreich, Adam Kalai, Sanjeev Khanna, Elad Haramaty, Clement Canonne, Venkatesan Guruswami, Raghu Meka, Badih Ghazi, Pritish Kamath, Ilan Komargodski, Pravesh Kothari, and Jacob Leshno.