57 Communication Complexity — Minimax

57.1 Overview

This module establishes Yao’s minimax principle for public-coin communication complexity. It introduces the distributional error of a deterministic protocol under an input distribution, proves a Fubini-type integral-swap lemma, and derives the key one-direction minimax bound: if every deterministic protocol of complexity at most \(n\) errs with probability greater than \(\varepsilon \) under some distribution \(\mu \) on \(X \times Y\), then the public-coin randomized communication complexity of \(f\) at error \(\varepsilon \) exceeds \(n\).

57.2 Declarations

Definition 57.1 Distributional error of a deterministic protocol

✓

Given a deterministic protocol \(p : \mathrm{Protocol}\, X\, Y\, \alpha \), a finite probability space \(\mu \) on \(X \times Y\), and a target function \(f : X \to Y \to \alpha \), the distributional error \(p.\mathrm{distributionalError}(\mu , f) \in \mathbb {R}\) is the \(\mu \)-probability that the output of \(p\) disagrees with \(f\), i.e. \(\mu \bigl(\{ (x,y) \mid p.\mathrm{run}(x,y) \ne f(x,y)\} \bigr)\).

Lemma 57.2 Swapping input and coin averages of the failure probability

✓

Suppose \(X\times Y\) is a finite probability space, whose probability measure we write \(\mathbb {P}\), let \(m\in \mathbb {N}\), and let \(p\) be a public-coin protocol whose shared randomness is a coin tape in \(\mathrm{CoinTape}(m)\), with Alice’s private input drawn from \(X\), Bob’s from \(Y\), and outputs in \(\alpha \). Write \(\mathrm{vol}\) for the measure on \(\mathrm{CoinTape}(m)\), and for a coin tape \(\omega \) and inputs \(x,y\) let \(\mathrm{rrun}(p,x,y,\omega )\) be the randomized execution of \(p\). Then for every function \(f\colon X\times Y\to \alpha \),

\[ \int _{\mathrm{CoinTape}(m)} \mathbb {P}\! \left(\bigl\{ (x,y)\in X\times Y : \mathrm{rrun}(p,x,y,\omega )\neq f(x,y)\bigr\} \right)\, d\omega = \int _{X\times Y} \mathrm{vol}\! \left(\bigl\{ \omega \in \mathrm{CoinTape}(m) : \mathrm{rrun}(p,x,y,\omega )\neq f(x,y)\bigr\} \right)\, d\mathbb {P}(x,y). \]

On the left one first measures, for each fixed coin tape \(\omega \), the \(\mathbb {P}\)-probability of the inputs on which \(p\) disagrees with \(f\), and then averages over \(\omega \); on the right one first measures, for each fixed input pair \((x,y)\), the set of coin tapes on which \(p\) disagrees with \(f\), and then averages over the inputs.

Theorem 57.3 Distributional lower bound for public-coin complexity

✓

Let \(f : X \to Y \to \alpha \) be a target function, let \(\varepsilon \in \mathbb {R}\), let \(n \in \mathbb {N}\), and let \(\mu \) be a finite probability space on \(X \times Y\). Suppose that every deterministic protocol \(p\) whose communication complexity is at most \(n\) has distributional error strictly greater than \(\varepsilon \) against \(f\) under \(\mu \); that is, the \(\mu \)-probability that \(p\) disagrees with \(f\) exceeds \(\varepsilon \). Then the \(\varepsilon \)-error public-coin randomized communication complexity of \(f\) is strictly greater than \(n\).