Lecture: Theory of Computing: CS | October 22 | 4-5 p.m. | Sutardja Dai Hall, Banatao Auditorium
Madhu Sudan, Harvard University
Reliable and efficient digital communication is possible today largely due to some wonderful successes in mathematical modelling and analysis. A legendary figure in this space is Claude Shannon (1916-2001) who laid out the mathematical foundations of communication in his seminal 1948 treatise, where among other contributions he gave a mathematical definition of "entropy" and coined the now ubiquitous term "bit" (for binary digit). But Shannon's theory is not the last word in communication. Communication extends to settings well beyond the carefully designed full information exchange model explored in Shannon's work. In this talk I will try to describe some of the many extensions that have been explored in the interim period including communication complexity (Yao 1980) that explores how it might be possible to achieve effective communication without a full exchange; interactive communication (Schulman 1992) which explores how to cope with errors in an interactive setting, and some of our own work on uncertain communication, which explores how shared context can make communication more effective, even if the context is shared only loosely.
Light refreshments will be served before the lecture at 3:30 p.m.