Abstract

Is it possible for two intelligent players to communicate meaningfully with each other, without any prior common background? What does it even mean for the two players to understand each other? In addition to being an intriguing question in its own right, we argue that this question also goes to the heart of modern communication infrastructures, where misunderstandings (mismatches in protocols) between communicating players are a major source of errors. We believe that questions like this need to be answered to set the foundations for a robust theory of (meaningful) communication.

In this talk, I will describe what computational complexity has to say about such interactions. Most of the talk will focus on how some of the nebulous notions, such as intelligence and understanding, should be defined in concrete settings. We assert that in order to communicate "successfully", the communicating players should be explicit about their goals - what the communication should achieve. We show examples that illustrate that when goals are explicit the communicating players can achieve meaningful communication.

Based on joint works with Oded Goldreich (Weizmann) and Brendan Juba (MIT).

Bio

Madhu Sudan recently joined Microsoft Research at their New England Research Center as a Principal Researcher. He is currently on leave from MIT where he was the Fujitsu Professor of EECS. 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. He joined MIT in 1997 where among other roles he was an Associate Director of MIT's CSAIL from 2007-2009.

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.