Communication amid uncertainty Madhu Sudan Microsoft Research New England 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. Communication of the bits have become reliable and increasingly, these bits are operated on, or operate, computers or mechanical devices. In such settings it becomes essential that the computers and machines know what the bits mean. In this talk we describe some of our attempts to extract the notion of meaning, and the challenges this task poses. The focus on meaning, and its misunderstanding, seems to emerge principally from "uncertainty". Senders and receivers are uncertain about what the other knows. 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.)