Abstract
The textbook example of the power of randomness in communication complexity is the Equality problem: with shared randomness, Alice and Bob can decide if their inputs x and y are equal using only O(1) bits of communication, independent of the input size. For which other problems is randomness so extremely effective? We will survey some results towards understanding this question, which has many connections to other areas like learning theory and graph theory.