Madhu Sudan
MIT
Towards Universal Semantic Communication
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 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 our approach towards this problem. We argue that in order to solve such problems, we 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 bachelor's degree from IIT Delhi in 1987 and his PhD 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 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.
Did you miss Madhu Sudan's lecture or would you like to hear it again? If so, just start the video below.
