We will study the amount of communication required to solve a problem when the input is distributed between two or more parties. As a prime example, consider the following game played by Alice and Bob: each player holds a string of length n, and the goal is to determine if the strings are equal by exchanging as little information as possible. For deterministic protocols, it is not hard to see that the players need to exchange n bits for information. However, allowing randomisation decreases this to only O(logn). As a more challenging example, each player holds a set, and the goal is to determine if the sets are disjoint.
While interesting in its own right as a clean and mathematically elegant model, communication complexity is important due to its applications in other areas. In this lecture, we will see how to use it to deduce lower bounds for data structures and streaming algorithms.
Basic knowledge of algorithms and data structure is necessary. Having already taken the Randomised algorithms course is advised but not required.
