55 Communication Complexity — Upper Bounds
55.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.
55.2 Declarations
For finite, nonempty types \(X\) and \(Y\) and any function \(f : X \to Y \to \alpha \), the deterministic communication complexity satisfies
This bound is achieved by the protocol in which Alice sends her entire input to Bob and Bob then sends his entire input to Alice.
For finite, nonempty types \(X\) and \(\alpha \) and any function \(f : X \to Y \to \alpha \), the deterministic communication complexity satisfies
This bound is achieved by the protocol in which Alice sends her input \(x\) to Bob, and Bob computes and sends back the output \(f(x, y)\).
For finite, nonempty types \(Y\) and \(\alpha \) and any function \(f : X \to Y \to \alpha \), the deterministic communication complexity satisfies
This bound is achieved by the protocol in which Bob sends his input \(y\) to Alice, and Alice computes and sends back the output \(f(x, y)\).