Communication Amid Uncertainty

Madhu Sudan (Harvard)

Societal aggregation of knowledge involves a mix of error-prone and error-correcting processes. Commmunication, or exchange of knowledge, leads to much of the errors, and this talk is motivated by the error-correction mechanisms (which include, but are not limited to, error-correcting codes and proofs). The main reason that communication leads to errors is not ``channel errors'' - such as spelling mistakes in the typing of this abstract. Instead errors arise from the use of shared context (such as language, mathematics, common knowledge) to compress communication, and fact that context is rarely perfecly shared.  Indeed it is remarkable that even in the absence of perfect sharing communication works quite effectively.

In this talk I will focus on some of our efforts to abstract shared context in communication and ability to communicate effectively even when context is not perfectly shared (using Yao's model of communication complexity as a starting point). In an attempt to connect to the theme of this workshop, I will also briefly introduce the concept of "contextual proofs" - where proofs are compressed by using (imperfectly) shared context ("we'll assume the reader is familiar with high school math") and the challenges that this seems to pose in communicating and verifying proofs - topics that we believe are ripe for further study using the tools of proof complexity.