69 Communication Complexity — Public Coin Complexity

69.1 Overview

This module defines the $\varepsilon $-error public-coin randomized communication complexity of a two-party function $f : X \to Y \to \alpha $ and establishes its basic structural properties: an existential characterization in terms of approximating protocols, equivalence with the finite-message formulation, and monotonicity in the error parameter $\varepsilon $.

69.2 Declarations

Definition 69.1 Public-coin communication complexity

✓

The $\varepsilon $-error public-coin randomized communication complexity of $f : X \to Y \to \alpha $ is defined as

\[ \mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \; =\; \inf _{\substack {n \in \mathbb {N},\; p \text{ a protocol on } \mathrm{CoinTape}(n) \\ p \text{ $\varepsilon $-approximates } f}} p.\mathrm{complexity}, \]

the infimum (in $\mathbb {N}_\infty $) of the worst-case bit complexity over all public-coin randomized protocols that compute $f$ with error at most $\varepsilon $ on every input.

Theorem 69.2 Characterization of complexity bound

✓

For $f : X \to Y \to \alpha $, $\varepsilon \in \mathbb {R}$, and $m \in \mathbb {N}$, we have $\mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \le m$ if and only if there exist $n \in \mathbb {N}$ and a public-coin protocol $p$ on $\mathrm{CoinTape}(n)$ such that $p$ $\varepsilon $-approximates $f$ and $p.\mathrm{complexity} \le m$.

Theorem 69.3 Lower bound characterization

✓

For $f : X \to Y \to \alpha $, $\varepsilon \in \mathbb {R}$, and $m \in \mathbb {N}$, we have $m \le \mathrm{R}^{\mathrm{pub}}_\varepsilon (f)$ if and only if every public-coin protocol $p$ on any $\mathrm{CoinTape}(n)$ that $\varepsilon $-approximates $f$ satisfies $m \le p.\mathrm{complexity}$.

Theorem 69.4 Finite-message characterization of complexity bound

✓

For $f : X \to Y \to \alpha $, $\varepsilon \in \mathbb {R}$, and $m \in \mathbb {N}$, we have $\mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \le m$ if and only if there exist $n \in \mathbb {N}$ and a finite-message public-coin protocol $p$ on $\mathrm{CoinTape}(n)$ such that $p$ $\varepsilon $-approximates $f$ and $p.\mathrm{complexity} \le m$. This shows that the binary-message and finite-message formulations of public-coin complexity coincide.

Theorem 69.5 Monotonicity in error

✓

Public-coin communication complexity is monotone in the error parameter: if $\varepsilon ' \le \varepsilon $, then $\mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \le \mathrm{R}^{\mathrm{pub}}_{\varepsilon '}(f)$. Allowing more error can only make computation easier.

Theorem 69.6 Upper bound from finite-message protocol on general probability space

✓

Let $\Omega $ be a finite probability space, $f : X \to Y \to \alpha $, and $\varepsilon ' \lt \varepsilon $. If a finite-message public-coin protocol $p$ over $\Omega $ computes $f$ with error at most $\varepsilon '$, then $\mathrm{R}^{\mathrm{pub}}_\varepsilon (f) \le p.\mathrm{complexity}$. This allows one to transfer upper bounds from protocols over arbitrary finite probability spaces to the coin-tape formulation.