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).

Decision Trees

One of the simplest models of computation is the decision tree model. In this model we are concerned with computing a function f: {0, 1}m → {0, 1} by using queries. Each query is given by specifying a function q on {0, l}m taken from some fixed family Q of allowed queries (the queries need not be Boolean). The answer given for the query is simply the value of q(x1, …, xm). The algorithm is completely adaptive, that is the i-th query asked may depend in an arbitrary manner on the answers received for the first i − 1 queries. The only wayto gain information about the input x is through these queries. The algorithm can therefore be described as a labeled tree, whose nodes are labeled by queries q ∈ Q, the outgoing edges of each node are labeled by the possible values of q(x1, …, xm), and the leaves are labeled by output values. Each sequence of answers describes a path in the tree to a node that is either the next query or the value of the output. In Figure 9.1 a decision tree is shown that computes (on inputs x1, …, x4) whether at least three of the input bits are 1s. It uses a family of queries Q consisting of all disjunctions of input variables and conjunctions of input variables.

The cost measure we are interested in is the number of queries performed on the worst case input; that is, the depth of the tree.

Definition 9.1: The decision tree complexity of a function f using the family of queries Q, denoted TQ(f), is the minimum cost decision tree algorithm over Q for f.

In Chapter 1 we saw that every communication protocol induces a partition of the space of possible inputs into monochromatic rectangles and learned of two lower bound techniques for the number of rectangles in such a partition. In this section we study how closely these combinatorial measures relate to communication complexity and to each other.

Covers and Nondeterminism

Although every protocol induces a partition of X × Y into f-monochromatic rectangles, simple examples show that the opposite is not true. In Figure 2.1, a partition of X × Y into monochromatic rectangles is given that do not correspond to any protocol. To see this, consider any protocol P for computing the corresponding function f. Since the function is not constant, there must be a first player who sends a message that is not constant. Suppose that this player is Alice. Since the messages that Alice sends on x, x′ and x″ are not all the same, there are two possibilities: (1) her messages on x and x′ are different. In this case the rectangle {x, x′} × {y} is not a monochromatic rectangle induced by the protocol P; or (2) her messages on x′ and x″ are different. In this case the rectangle {x′, x″} × {y″} is not a monochromatic rectangle induced by the protocol P. Similarly, if Bob is the first player to send a nonconstant message, then this message is inconsistent with either the rectangle {x} × {y′, y″) or with the rectangle {x″} × {y, y′}.