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 misundestandings (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.

Joint work with Brendan Juba (MIT).

Biography：

Madhu Sudan received his Bachelor's degree from the Indian Institute of Technology at New Delhi in 1987 and his  Ph.D.  from the University of California at Berkeley in 1992. From 1992-1997 he was a Research Staff Member at IBM's Thomas J. Watson Research Center. In 1997, he moved to MIT where he is now the Fujitsu Professor of Electrical Engineering and Computer Science, and as Associate Director of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). He was a Fellow at the Radcliffe Institute for Advanced Study from 2003-2004, and a Guggenheim Fellow from 2005-2006.

Madhu Sudan's research interests include computational complexity theory, algorithms and coding theory. He is best known for his works on probabilistic checking of proofs, and on the design of list-decoding algorithms for error-correcting codes. He has served on numerous program committees for conferences in theoretical computer science, and was the program committee chair   of the IEEE Conference on Computational Complexity '01, and the IEEE Symposium on Foundations of Computer Science '03.  He is the chief editor of Foundations and Trends in Theoretical Computer Science, a new journal publishing surveys in the field. He is currently a member of the editorial boards of the Journal of the ACM and the SIAM Journal on Computing. Previously he served on the boards of the SIAM Journal on Discrete Mathematics, Information and Computation, and the IEEE Transactions on Information Theory.