Communication amid uncertainty

The classical theory of communication, starting with the work of Shannon, has always that assumed the meaning of the messages being exchanged is known to the sender and receiver. This assumption set aside a tricky issue and allowed the theory to focus on the more pressing engineering problem of the time - namely communicating the bits efficiently and reliably. In the current times, we see increasing evidence that this question can no longer be set aside. On the one hand, communication of the bits have become very reliable, so reliability is no longer the pressing concern today. On the other hand, increasingly these bits are operated on by computers or mechanical devices. In such settings it becomes essential that the computers and machines know what the bits mean. In this article intended to accompany a talk to be given at the workshop, we describe some of our attempts to extract the notion of meaning, and the challenges this task poses. Meaning is best understood by focussing on the phenomenon of “misunderstanding”, i.e., when the receiver does not understand what the sender says. Misunderstanding, in turn, seems to emerge principally from “uncertainty”: Senders and receivers are uncertain about what the other knows/believes. We illustrate the problem in a simple setting, before moving on to describing our attempts to tackle the general complex task. Based on joint works with Brendan Juba (Harvard), Oded Goldreich (Weizmann), Adam Kalai (MSR New England), and Sanjeev Khanna (U. Penn.).