52 Communication Complexity — Upper Bounds
52.1 Overview
This module establishes elementary upper bounds on the deterministic communication complexity of a two-party function \(f : X \times Y \to \alpha \). Each bound is witnessed by an explicit protocol (Alice or Bob sends their raw input, and the other party replies with the output) and is expressed in terms of the ceiling-logarithm \(\lceil \log _2 n \rceil \) of the relevant cardinality.
52.2 Declarations
Let \(X\) and \(Y\) be finite nonempty types, let \(\alpha \) be any type, and let \(f : X \to Y \to \alpha \). Then the deterministic communication complexity of \(f\) satisfies
where \(\left\lvert X\right\rvert \) and \(\left\lvert Y\right\rvert \) denote the cardinalities of \(X\) and \(Y\).
Let \(X\) and \(\alpha \) be finite nonempty types, let \(Y\) be an arbitrary type, and let \(f : X \to Y \to \alpha \) be a two-argument function. Then the deterministic communication complexity of \(f\) satisfies
where \(\left\lvert X\right\rvert \) and \(\left\lvert \alpha \right\rvert \) denote the cardinalities of \(X\) and \(\alpha \).
Let \(X\) be an arbitrary type and let \(Y\) and \(\alpha \) be finite nonempty types. Then for every function \(f : X \to Y \to \alpha \), the deterministic communication complexity of \(f\) satisfies
where \(\left\lvert Y\right\rvert \) and \(\left\lvert \alpha \right\rvert \) denote the cardinalities of \(Y\) and \(\alpha \).
52.3 Additional declarations
Let \(f : X \to Y \to \alpha \) and let \(p\) be a finite-message protocol over \(X\), \(Y\), \(\alpha \) whose run function equals \(f\). Then for every \(c \in \mathbb {N} \cup \{ \infty \} \) with \(\texttt{FiniteMessage.Protocol.complexity}\, (p) \le c\), the deterministic communication complexity of \(f\) satisfies \(D(f) \le c\). Each of the three public bounds above is a single application of this lemma to an explicit two-message protocol.