64 Communication Complexity — Private Coin Complexity
64.1 Overview
This module defines the \(\varepsilon \)-error private-coin randomized communication complexity of a two-party function \(f : X \to Y \to \alpha \) and establishes its basic characterization theorems: a bound-below criterion, a bound-above criterion, an equivalent formulation via finite-message protocols over arbitrary finite probability spaces, and monotonicity in the error parameter \(\varepsilon \).
64.2 Declarations
The \(\varepsilon \)-error private-coin randomized communication complexity of \(f : X \to Y \to \alpha \) is the extended natural number
i.e. the minimum worst-case number of bits exchanged over all private-coin randomized protocols that compute \(f\) with error at most \(\varepsilon \) on every input.
For any \(n \in \mathbb {N}\), we have \(R_\varepsilon (f) \le n\) if and only if there exist coin-tape sizes \(n_X, n_Y \in \mathbb {N}\) and a protocol \(p : \mathrm{Protocol}(\{ 0,1\} ^{n_X}, \{ 0,1\} ^{n_Y}, X, Y, \alpha )\) such that \(p\) \(\varepsilon \)-approximately computes \(f\) and \(p.\mathrm{complexity} \le n\).
For any \(n \in \mathbb {N}\), we have \(n \le R_\varepsilon (f)\) (in \(\mathbb {N}_\infty \)) if and only if every private-coin protocol \(p\) over coin tapes of any size that \(\varepsilon \)-approximately computes \(f\) satisfies \(n \le p.\mathrm{complexity}\).
For any \(n \in \mathbb {N}\), \(R_\varepsilon (f) \le n\) if and only if there exist coin-tape sizes \(n_X, n_Y \in \mathbb {N}\) and a finite-message protocol \(p : \mathrm{FiniteMessage.Protocol}(\{ 0,1\} ^{n_X}, \{ 0,1\} ^{n_Y}, X, Y, \alpha )\) such that \(p\) \(\varepsilon \)-approximately computes \(f\) and \(p.\mathrm{complexity} \le n\). This establishes that passing to the finite-message variant does not change the complexity measure.
If \(\varepsilon ' \le \varepsilon \), then \(R_\varepsilon (f) \le R_{\varepsilon '}(f)\). In other words, the private-coin communication complexity is monotone decreasing in the error parameter: permitting more error can only reduce (or preserve) the required communication.
Let \(\Omega _X\) and \(\Omega _Y\) be finite probability spaces and let \(p : \mathrm{FiniteMessage.Protocol}(\Omega _X, \Omega _Y, X, Y, \alpha )\) be a finite-message protocol that \(\varepsilon '\)-approximately computes \(f\). If \(\varepsilon ' \lt \varepsilon \), then \(R_\varepsilon (f) \le p.\mathrm{complexity}\). This is the key reduction step showing that protocols over arbitrary finite probability spaces witness upper bounds on the private-coin complexity.