5 - The Communication Complexity of Relations

Summary

In the first part of this book we were interested in computing functions. That is, for any input (x, y) there was a unique value f(x, y) that Alice and Bob had to compute. More general types of problems are relations. In this case, on input (x, y) there might be several values that are valid outputs. Formally,

Definition 5.1:A relation R is a subset R ⊆ X × Y × Z. The communication problem R is the following: Alice is given x ∈ X, Bob is given y ∈ Y, and their task is to find some z ∈ Z that satisfies the relation. That is, (x, y, z) ∈ R.

Note that functions are a special case of the above definition, where z is uniquely defined. Also note that it may be the case that for a certain input pair (x, y) there is no value z such that (x, y, z) ∈ R. We say that this input is illegal and we assume that it is never given as an input to Alice and Bob. Alternatively, we can assume that for every (x, y) there must exist a possible value z. For example, by extending the relation R and allowing every output z for the illegal pairs (that is, (x, y, z) ∈ R for all z ∈ Z).