61 Communication Complexity — One Way Minimax

61.1 Overview

This module establishes Yao’s minimax principle for one-way public-coin communication protocols. It introduces the distributional error of a deterministic one-way protocol and proves that if every deterministic protocol of cost at most \(n\) suffers distributional error exceeding \(\varepsilon \) under some joint input distribution, then the one-way public-coin communication complexity at error \(\varepsilon \) exceeds \(n\).

61.2 Declarations

Definition 61.1 Distributional error of a one-way protocol

✓

Given a deterministic one-way protocol \(p\) computing a function \(f : X \to Y \to \alpha \), and a finite probability distribution \(\mu \) on \(X \times Y\), the distributional error of \(p\) with respect to \(\mu \) and \(f\) is the real number

\[ \Pr _{(x,y)\sim \mu }\bigl[p.\mathrm{run}(x,y) \neq f(x,y)\bigr], \]

i.e. the \(\mu \)-measure of the set of inputs on which the protocol’s output disagrees with \(f\).

Definition 61.2 Deterministic protocol from public-coin protocol

✓

Given a one-way public-coin protocol \(p\) over a randomness space \(\Omega \) and a fixed coin outcome \(\omega \in \Omega \), toDeterministic \(p\) \(\omega \) is the deterministic one-way protocol obtained by substituting \(\omega \) for the public randomness: it uses the same message type and sends/decodes by fixing \(\omega \) in \(p\).

Theorem 61.3 Run of derandomised protocol

✓

For any public-coin protocol \(p\), coin outcome \(\omega \), and inputs \(x \in X\), \(y \in Y\),

\[ (p.\mathrm{toDeterministic}(\omega )).\mathrm{run}(x, y) \; =\; p.\mathrm{rrun}(x, y, \omega ). \]

That is, running the derandomised protocol on \((x,y)\) agrees with running the randomised protocol on \((x,y)\) with fixed randomness \(\omega \).

Theorem 61.4 Cost of derandomised protocol

✓

For any public-coin protocol \(p\) and coin outcome \(\omega \),

\[ (p.\mathrm{toDeterministic}(\omega )).\mathrm{cost} \; =\; p.\mathrm{cost}. \]

Fixing the randomness does not change the communication cost of the protocol.

Lemma 61.5 Fubini swap for failure integrals

✓

Let \(\mu \) be a finite probability measure on \(X \times Y\), let \(p\) be a one-way public-coin protocol with coin tape of length \(m\), and let \(f : X \to Y \to \alpha \). Then

\[ \int _{\omega }\Pr _{(x,y)\sim \mu }\bigl[p.\mathrm{rrun}(x,y,\omega )\neq f(x,y)\bigr]\, d\omega \; =\; \int _{(x,y)\sim \mu }\Pr _{\omega }\bigl[p.\mathrm{rrun}(x,y,\omega )\neq f(x,y)\bigr]\, d\mu , \]

i.e. the order of integration over the coin tape and the input distribution may be exchanged (Fubini’s theorem applied to the \(\{ 0,1\} \)-valued failure indicator).

Theorem 61.6 Yao’s minimax principle for one-way protocols

✓

Let \(f : X \to Y \to \alpha \), \(\varepsilon \in \mathbb {R}\), and \(n \in \mathbb {N}\). Suppose there exists a finite joint distribution \(\mu \) on \(X \times Y\) such that every deterministic one-way protocol \(p\) with \(p.\mathrm{cost} \le n\) satisfies \(p.\mathrm{distributionalError}(\mu , f) \gt \varepsilon \). Then the one-way public-coin communication complexity of \(f\) at error \(\varepsilon \) satisfies \(n \lt \mathrm{communicationComplexity}(f, \varepsilon )\). This is one direction of Yao’s minimax principle: a hard input distribution witnesses a lower bound on randomised complexity.