Abstract:

Communication complexity asks the following question: we have two players, traditionally called Alice and Bob, and each player has a private input X,Y. The players want to compute some joint function f(X,Y) of their inputs. To do so, they need to communicate. How many bits do they need to send each other to compute a particular f?

Lower bounds on the communication complexity of various functions give us lower bounds in practically every area of theoretical computer science, from circuit lower bounds to data structures and distributed computing. In this talk I'll show a few simple communication lower bounds, and how they can be applied to get lower bounds in other areas.