Tutorial: Communication Complexity: New Results and Directions

In this survey talk we will review the basics of communication complexity, and then discuss the following exciting directions from the last few years. We will discuss information complexity, its close connection with communication complexity, and many of the important results that have been proven in this area in the last five years. New lower bounds on the communication complexity of search problems, and applications including very strong monotone circuit lower bounds, as well as proof complexity lower bounds. The last five years has seen some very exciting results in the area of Extended Formulations. It is now known that no linear or semi-definite extended formulation can solve or even approximate many NP-hard problems. Moreover, these lower bounds are tightly connected to a new communication model where the protocol only needs to output the correct value in expectation (over the randomness of the protocol). We will discuss this connection, and survey what is known about lower bounds.

Authors

• Toni Pitassi University of Toronto

Keywords

No keywords are indexed for this paper.