60 Communication Complexity — Minimax

60.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\).

60.2 Declarations

Definition 60.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 60.2 Failure integral swap

✓

Let \(\mu \) be a finite probability space on \(X \times Y\), let \(m \in \mathbb {N}\), and let \(p\) be a public-coin protocol with coin tape of length \(m\). For any \(f : X \to Y \to \alpha \),

\[ \int _{\omega }\, \mu \! \left(\bigl\{ (x,y) \mid p.\mathrm{rrun}(x,y,\omega ) \ne f(x,y)\bigr\} \right)\, d\omega \; =\; \int _{(x,y)}\, \mathrm{vol}\! \left(\bigl\{ \omega : \mathrm{CoinTape}\, m \mid p.\mathrm{rrun}(x,y,\omega ) \ne f(x,y)\bigr\} \right)\, d\mu , \]

obtained by swapping the order of integration via Fubini’s theorem applied to the failure-indicator function.

Theorem 60.3 Yao’s minimax principle

✓

Let \(f : X \to Y \to \alpha \), \(\varepsilon \in \mathbb {R}\), \(n \in \mathbb {N}\), and let \(\mu \) be a finite probability distribution on \(X \times Y\). If every deterministic protocol \(p\) with \(p.\mathrm{complexity} \le n\) satisfies \(p.\mathrm{distributionalError}(\mu , f) \gt \varepsilon \), then the public-coin randomized communication complexity of \(f\) at error \(\varepsilon \) is strictly greater than \(n\). This is one direction of Yao’s minimax principle: a hard distribution for all small deterministic protocols certifies a lower bound on randomized complexity.