Tata Institute of Fundamental Research
(Deterministic) Communication Amid Uncertainty
Colloquium
Speaker:
Madhu Sudan (Microsoft Research New England)
Date:
Tuesday, 20 Nov 2012, 14:00 to 15:00
Venue:
AG69
(Scan to add to calendar)
Abstract:
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.)
| Speaker: | Madhu Sudan (Microsoft Research New England) |
| Date: | Tuesday, 20 Nov 2012, 14:00 to 15:00 |
| Venue: | AG69 |
(Scan to add to calendar)
Abstract:
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.)