Communication and information complexity

Abstract

Communication complexity is an area of computational complexity theory that studies the amount of communication required to complete a computational task. Communication complexity gives us some of the most successful techniques for proving impossibility results for computational tasks.

Information complexity connects communication complexity with Shannon’s classical information theory. It treats information revealed or transmitted as the resource to be conserved. On the one hand, information complexity leads to extensions of classical information and coding theory to interactive scenarios. On the other hand, it provides us with tools to answer open questions about communication complexity and related areas. This note gives an overview of communication complexity and some recent developments in two-party information complexity and applications. The note is based on a talk given by the author at the International Congress of Mathematicians in 2022. It expands on some of the themes from the talk. It also provides references that were omitted during the talk.