This project expands classical information and coding theories to the interactive communication settings. Information and coding theories give us a near-perfect understanding of the capacity of networks, such as the Internet or mobile networks, to transmit information. This understanding however, is generally limited to the non-interactive setting: there is a sender and a receiver and the goal is to transmit a message from the sender to the receiver as quickly and reliably as possible. In recent years, applications such as cloud computing gave rise to interactive communication problems, where the goal is to implement a whole functionality over a communication channel, rather than just transmit data. The investigators study fundamental questions surrounding extending information theory approaches to interactive problems. The project aims to establish the limits of interactive computation, as well as to develop new encoding algorithms that make interactive computing more efficient.
The key technical concept being developed by the investigators is that of information complexity. Information complexity is the natural generalization of Shannon's entropy to interactive problems. Shannon's entropy measures the amount of information contained in a random message. Interactive information complexity measures the amount of information contained in the interactive computation, as perceived by the participating parties. The project develops this concept to address problems in communication complexity, such as direct sum theorems, multi-party communication complexity, and hardness amplification. More broadly, the investigators develop techniques for applying information theory to computational complexity, with the aim of expanding the technical toolbox available to attack fundamental problems in complexity theory.
