Chennai Mathematical Institute

Seminars




2.00 pm, NKN Hall
CMI Silver Jubilee Lecture
Communication Amid Uncertainty

Madhu Sudan
MIT and Microsoft Research, USA.
06-01-15


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. Players learn to coordinate on future actions (under mild conditions) even in the absence of prior understanding of each other's future plans.

Based on joint works with Brendan Juba (Washington U.), Oded Goldreich (Weizmann), Adam Kalai (MSR), Sanjeev Khanna (U. Penn.), Elad Haramaty (Technion), Clement Canonne (Columbia), Venkatesan Guruswami (CMU), Raghu Meka (UCLA), and Jacob Leshno (Columbia).