Communication Amid Uncertainty

10 Nov
Computer Science Colloquium Series
Madhu Sudan, Microsoft Research New England
Monday, November 10, 2014 -
4:00pm to 5:15pm
Maxwell Dworkin G115

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).

Speaker Bio: 

Madhu Sudan got his Bachelors degree from IIT Delhi in 1987 and his Ph.D. from UC Berkeley in 1992. From 1992-1997 he was a Research Staff Member at IBM's Thomas J. Watson Research Center. In 1997 he joined the faculty at MIT, where among other roles he served as an Associate Director of MIT's CSAIL from 2007-2009. In 2009, Madhu Sudan joined Microsoft Research at their New England Research Center as a Principal Researcher. He continues to be an Adjunct Professor at MIT.

Madhu Sudan's research lies in the fields of computational complexity theory, algorithms and reliable communcation. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. His current research interests include semantic communication and property testing. In 2002, Madhu Sudan was awarded the Nevanlinna Prize, for outstanding contributions to the mathematics of computer science, at the International Congress of Mathematicians in Beijing.

Salil Vadhan
Meg Hastings