Joint Colloquium Distinguished Lecture Series
Towards Universal Semantic Communication
 |
Wednesday, September 22, 2010 Madhu Sudan |
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? We claim that this question, in addition to being of philosophical/linguistic interest, goes to the essence of modern communication/computation. Modern communicating devices are extremely diverse, constantly evolving, and misunderstandings (mismatches in protocols) between communicating devices are inevitable and a major source of errors. The questions raised above need to be answered to set the foundations for a robust theory of (meaningful) communication - one that would cover such diverse & evolving communicating devices.
In this talk, I will describe our approach towards this problem. We argue that in order to get to the heart of such questions, one must first articulate why intelligent players (and/or powerful computers) communicate. This leads us to a formal theory of "goals" of communication. We then show that when progress towards the goal is "verifiable'' then players can detect misunderstandings. Under a complexity-theoretic lens, we show roughly that verifiability is really the essence of resolving misunderstandings: Verifiable goals are more powerful than goals that can be achieved without communication (so communication is good), but very restricted compared to ``unverifiable'' goals (so there is need for moderation). Most of the talk will focus on the definitions of various concepts such as ``goals'', ``(mis)understanding'' and resort to theorems based on computational complexity to support these definitions.
Based on joint works with Oded Goldreich (Weizmann) and Brendan Juba (MIT).
Biography
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.
| Return to EECS Joint Colloquium |