Communication complexity

Definition

Let $X$ and $Y$ be finite sets and let $f \colon X \times Y \to \set{0, 1}$ be a function. A deterministic protocol for $f$ is a rooted binary tree with these labels.

1. Each internal node is owned by Alice or by Bob.
2. An internal node owned by Alice carries a map $a \colon X \to \set{0, 1}$, and one owned by Bob carries a map $b \colon Y \to \set{0, 1}$.
3. Each leaf carries an output in $\set{0, 1}$.

On input $(x, y)$, the run starts at the root. At each internal node it applies the map of the node to $x$ or to $y$. It goes to the left child if the value is $0$, and to the right child if it is $1$. The protocol computes $f$ if for every $(x, y)$ the run ends at a leaf whose label is $f(x, y)$. The cost of the protocol is the depth of the tree, the number of bits sent in the worst case. The deterministic communication complexity $D(f)$ is the least cost of a protocol that computes $f$.