50 Communication Complexity — One Way
50.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.
50.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.
For any one-way protocol \(p\) and inputs \((x, y)\), running \(p\)’s embedding in the finite-message model yields the same output as running \(p\) directly: \(\mathtt{FiniteMessage.Protocol.run}(p.\mathtt{toFiniteMessage},\, x,\, y) = p.\mathtt{run}(x, y)\).
The interactive complexity of the embedding equals the one-way cost plus the cost for Bob to transmit the decoded output: \((p.\mathtt{toFiniteMessage}).\mathtt{complexity} = p.\mathtt{cost} + \lceil \log _2 |\alpha | \rceil \).
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\).
For a function \(f\) and \(n \in \mathbb {N}\), the one-way complexity of \(f\) is at most \(n\) if and only if there exists a one-way protocol \(p\) that computes \(f\) with \(p.\mathtt{cost} \le n\).
For a function \(f\) and \(k \in \mathbb {N}\), \(k\) is at most the one-way complexity of \(f\) if and only if every one-way protocol \(p\) computing \(f\) satisfies \(k \le p.\mathtt{cost}\).
If the one-way communication complexity of \(f : X \to Y \to \alpha \) is at most \(n\), then the (interactive) deterministic communication complexity of \(f\) is at most \(n + \lceil \log _2 |\alpha | \rceil \), with the additive term accounting for Bob’s cost of transmitting the decoded output in the interactive model.
For a Boolean function \(f : X \to Y \to \mathtt{Bool}\), if the one-way complexity of \(f\) is at most \(n\), then the deterministic complexity of \(f\) is at most \(n + 1\); this specializes the general bound using \(\lceil \log _2 |\mathtt{Bool}| \rceil = 1\).