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? In most case we have only partial results, and I will describe what we know and the many open questions.
Based on joint works with Clement Canonne, Badih Ghazi, Oded Goldreich, Venkatesan Guruswami, Elad Haramaty, Brendan Juba, Adam Kalai, Pritish Kamath, Sanjeev Khanna, Ilan Komargodski, Pravesh Kothari, Jacob Leshno, and Raghu Meka.
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 communication. 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.
