47 Communication Complexity — One Way
47.1 Overview
This module develops one-way deterministic communication protocols, in which Alice sends a single message from a finite codebook and Bob produces the output. The main results relate the one-way communication complexity of a function to its standard (interactive) deterministic communication complexity, with an additive \(\lceil \log _2 |\alpha | \rceil \) overhead for Bob to transmit the decoded output.
47.2 Declarations
A one-way deterministic communication protocol for inputs \(x \in X\), \(y \in Y\), and output type \(\alpha \) is a structure consisting of a finite, nonempty message codebook Message, Alice’s encoder \(\mathtt{send} : X \to \mathtt{Message}\) that selects a codeword from the codebook based solely on her input, and Bob’s decoder \(\mathtt{decode} : \mathtt{Message} \times Y \to \alpha \) that produces the final output from the received message and his own input.
Given a one-way protocol \(p\) and inputs \(x \in X\), \(y \in Y\), executing the protocol yields the output \(p.\mathtt{decode}(p.\mathtt{send}(x),\, y) \in \alpha \).
The communication cost of a one-way protocol \(p\) is \(\lceil \log _2 |\mathtt{Message}| \rceil \) bits, where \(\mathtt{Message}\) is the protocol’s codebook.
A one-way protocol \(p\) computes a function \(f : X \to Y \to \alpha \) if \(p.\mathtt{run}(x, y) = f(x, y)\) for every pair of inputs \((x, y)\).
Given a one-way protocol \(p\) with finite output type \(\alpha \), one obtains an interactive finite-message protocol by having Alice send her one-way message and then having Bob encode the decoded output as an index in \(\{ 0,\ldots ,|\alpha |-1\} \) and transmit it.
Let \(p\) be a one-way deterministic communication protocol over input types \(X\), \(Y\) and a finite, nonempty output type \(\alpha \), and let \(x \in X\) and \(y \in Y\). Then executing the finite-message protocol obtained from \(p\) by the embedding into the finite-message model on the inputs \(x\) and \(y\) yields the same element of \(\alpha \) as executing \(p\) directly on \(x\) and \(y\).
Let \(p\) be a one-way deterministic communication protocol with inputs in \(X\), \(Y\) and output type \(\alpha \), and suppose \(\alpha \) is finite and nonempty. The finite-message protocol obtained from \(p\) — Alice sends her one-way message, after which Bob transmits the decoded output as an index in \(\{ 0,\ldots ,\left\lvert \alpha \right\rvert -1\} \) — has communication complexity
that is, the bit cost of \(p\) plus \(\lceil \log _2 \left\lvert \alpha \right\rvert \rceil \), where \(\mathrm{Message}\) is the codebook of \(p\).
The one-way deterministic communication complexity of \(f : X \to Y \to \alpha \) is the infimum (in \(\mathbb {N}_\infty \)) of the bit costs \(p.\mathtt{cost}\) over all one-way protocols \(p\) that compute \(f\).
Let \(f : X \to Y \to \alpha \) be a function and let \(n \in \mathbb {N}\). The one-way deterministic communication complexity of \(f\) is at most \(n\) if and only if there exists a one-way deterministic protocol \(p\) that computes \(f\) and whose bit cost satisfies \(\mathrm{cost}(p) \le n\).
Let \(f : X \to Y \to \alpha \) be a function and let \(k \in \mathbb {N}\). Then \(k\) is at most the one-way deterministic communication complexity of \(f\) (as an inequality in \(\mathbb {N}_\infty \)) if and only if every one-way deterministic protocol that computes \(f\) has bit cost at least \(k\).
Let \(f : X \to Y \to \alpha \) be a two-argument function whose output type \(\alpha \) is finite and nonempty, and let \(n \in \mathbb {N}\). If the one-way deterministic communication complexity of \(f\) is at most \(n\), then the (interactive) deterministic communication complexity of \(f\) is at most \(n + \lceil \log _2 \left\lvert \alpha \right\rvert \rceil \).
Let \(X\) and \(Y\) be the input types of Alice and Bob, and let \(f : X \to Y \to \mathrm{Bool}\) be a two-party Boolean-valued function. If the one-way deterministic communication complexity of \(f\) is at most \(n\) for some \(n \in \mathbb {N}\), then the (interactive) deterministic communication complexity of \(f\) is at most \(n + 1\).
47.3 Additional declarations
The ceiling of the base-\(2\) logarithm of \(2\) equals \(1\): in Lean’s natural-number ceiling logarithm, \(\lceil \log _2 2 \rceil = 1\). This is the numeric fact used to specialize the additive \(\lceil \log _2 \left\lvert \alpha \right\rvert \rceil \) overhead to \(1\) for Boolean-valued functions.