CMI Silver Jubilee Lecture
Madhu Sudan, MIT and Microsoft Research, USA
Communication Amid Uncertainty
Tuesday, January 6, 2015
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
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).