(Deterministic) Communication Amid Uncertainty


Madhu Sudan


Microsoft Research New England


Tuesday, 20 November 2012, 14:00 to 15:00


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.)