Lecture: Mathematical Theories of Communication: Old and New

Madhu Sudan

Abstract:

Reliable and efficient digital communication today is possible largely in part 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 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.

---