Interactive Information Complexity and Applications

Abstract

With applications in nearly every field of computer science, Communication Complexity constitutes one of the most useful methods for proving unconditional lower bounds - the holy grail of complexity theory. Developing tools in communication complexity is

a promising approach for making progress in other computational models such as streaming, property testing, distributed computing, circuit complexity and data structures. One striking example of such tool is Shannon's information theory, introduced in

the late 1940's in the context of the one way data transmission problem. While revealing the intimate connection between information and communication, Shannon's work and its classical extensions do not readily convert to interactive setups such as the communication complexity model, where two parties must engage in a multi-round conversation to accomplish some desirable interactive task.

The research presented in this monograph aspires to extend Shannon's theory, develop the right tools, and understand how information behaves in interactive setups. The main measure if interest is the Interactive Information Complexity of a function, which informally captures the least amount of information the parties need to disclose each other about their inputs in order to solve the underlying task. We develop information-theoretic tools with applications to some of the most fundamental questions in communication complexity, including the limits of parallel computation, interactive compression, and the KRW conjecture. We then demonstrate the power of information complexity beyond communication complexity, with applications to various theoretical models, including data streaming, circuit lower bounds, privacy and economics. Lurking beneath these results is the fascinating question about the role of interaction and information in obtaining efficient outcomes, where efficiency may be measured in terms of social welfare, space, privacy or communication, depending on the model and context.