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.

In this talk we will give an overview of communication complexity, some connections to two-party information complexity and applications, as well as open problems and directions.