Room 327

Information Complexity in Communication Complexity

Prahladh Harsha

TIFR

Information complexity of a two-party function f(x,y) is the minimum amount of information revealed by two parties Alice (who has input x) and Bob (who has input y) to jointly compute the function f(x,y). Since it was introduced by Chakraborty, Su, Wirth and Yao to study the direct sum question in communication complexity, information complexity has been a very powerful tool to understand the communication complexity of several functions. The last 1-2 years have seen several results related to information complexity, showing the power of this tool (in particular, that it is almost as powerful as all other existing tools in communication complexity, like discrepancy, norm-based approaches, partition bounds etc).

I'll survey some of these recent results during the course of the three lectures outlining the various methods and highlighting some of the open questions in the area.

The lectures will be accessible to anyone interested in complexity. In particular, no prior knowledge of communication complexity will be assumed.