Professor Anup Rao of UW CSE’s Theory group has been recognized by the Society for Industrial and Applied Mathematics (SIAM) with its Outstanding Paper Prize for the 2013 paper, How to Compress Interactive Communication. Each year, SIAM selects just three papers from among thousands published in its journals over the previous three years for the award, which honors authors who have made original contributions to the field of applied mathematics.
In 1948, Claude E. Shannon published his foundational paper on information theory. He defined the entropy of a message, and showed that this quantity captures the number of bits required for one party to communicate the message to another, thereby laying the mathematical groundwork for the field of data compression.
Shannon’s result addresses the setting of one-way communication tasks. But what if two parties engage in a conversation, possibly exchanging many short messages in order to accomplish a task interactively. Can such a protocol be compressed? If so, what is the appropriate notion of entropy?
The groundbreaking paper by Rao and co-authors Boaz Barak, Mark Braverman, and Xi Chen, addresses precisely these questions. They present sophisticated methods to compress interactive communication protocols. Intuitively, their idea is for the communicating parties to predict the future communication transcript based on their current partial knowledge. Moreover, they put forth a precise and appealing definition of the “information cost” of a protocol which measures the amount of information exchanged by the two parties.
The team’s work helped to launch the field of information complexity, and led to progress in many areas of computer science, including streaming computation, differential privacy, communication complexity, and quantum communication.
Learn more about the award here, and read the winning paper here.
Congratulations, Anup!