Consider the following problem: two people each have a binary string of length n. They would like to know whether or not their strings are equal. What's the minimum amount of information that they must exchange to do this?
As another problem: two people each have a set of numbers. They would like to know the average of their combined list of numbers. What's the minimum amount of information they need to exchange to do this?
The problems above are examples of the relatively young field of communication complexity. In this talk we will survey the resulting linear algebraic and combinatorial problems that arise from Communication Complexity, and describe some surprising, recent results in Communication Complexity.
|