(Deterministic) Communication Amid Uncertainty

Madhu Sudan
(MSR New England)

Most natural communication among humans is characterized by a lack of
perfect understanding among the communicating players. Arguably this
lack of perfect understanding plays a significant role in the development
of human languages, which tend to have bendable rules,
ambiguous dictionaries, and seemingly needless redundancies. In this
series of works we explore one question that arises from such communication
amid uncertainty.

We consider a case of a sender of information attempting to compress
information before sending it to the receiver, in a setting where
the sender and receiver have moderate, but not perfect, agreement
on the distribution from which the message is chosen. In case of
perfect agreement, a scheme like Huffman coding would compress the
information down to its entropy. What happens with imperfect agreement?
We will show some randomized and deterministic schemes that achieve
some non-trivial compression. We will mention some intriguing open
problems in the deterministic setting (which we believe to be harder
and possibly more insightful in this setting).


Based on joint works with Elad Haramaty (Technion),  Brendan Juba (MIT/Harvard),
Adam Kalai (MSR), and Sanjeev Khanna (U.Penn.)