81 Communication Complexity — Newman Theorem
81.1 Overview
This module establishes Newman’s theorem: every public-coin communication protocol can be converted into a private-coin protocol with only \(O(\log (|X| \cdot |Y|) / \varepsilon ^2)\) additional bits of communication. The key construction is the Newman protocol, which has Alice sample a random index into a fixed table of good random seeds (chosen via a Chernoff and union-bound argument) and send that index to Bob, after which both parties simulate the original public-coin protocol deterministically.
81.2 Declarations
Given finite input types \(X\) and \(Y\) and parameters \(\varepsilon , c \in \mathbb {R}\), the Newman index space is \(\mathrm{Fin}(\mathtt{derandomizationSamples}\; X\; Y\; \varepsilon \; c)\), i.e. the finite type indexing the table of random seeds that Alice samples from in the Newman reduction.
Given a public-coin finite-message protocol \(p\) over a probability space \(\Omega \) that \(\varepsilon \)-computes \(f : X \to Y \to \alpha \), and a constant \(c \gt 1\), the Newman protocol is a private-coin finite-message protocol in which Alice draws a random index \(i\) from \(\mathtt{newmanIndexSpace}\; X\; Y\; \varepsilon \; c\) and sends it to Bob; both players then run the \(i\)-th seed from a fixed table of good randomness values (obtained via a Chernoff and union-bound argument) through the original public-coin protocol deterministically.
Let \(\Omega \) be a finite probability space, let \(X\) and \(Y\) be finite types, and let \(p\) be a public-coin finite-message protocol over shared randomness \(\Omega \) with inputs in \(X\) and \(Y\) and outputs in a type \(\alpha \). Fix a target function \(f : X \times Y \to \alpha \), a real error bound \(\varepsilon \), and a real constant \(c \gt 1\), and suppose that \(p\) \(\varepsilon \)-computes \(f\), meaning that for every input pair \((x,y)\) the probability over the shared randomness that \(p\) outputs something other than \(f(x,y)\) is at most \(\varepsilon \). Then the associated Newman protocol — the private-coin protocol in which Alice draws an index into the fixed table of good random seeds, sends it to Bob, and both run \(p\) deterministically on that seed — \((c\varepsilon )\)-computes \(f\): for every input pair \((x,y)\) the probability over the private randomness that its output differs from \(f(x,y)\) is at most \(c\varepsilon \).
Let \(X\) and \(Y\) be finite types, let \(\Omega \) be a finite probability space, and let \(p\) be a public-coin finite-message protocol over \(\Omega \) with private inputs in \(X\) and \(Y\) and outputs in a type \(\alpha \). Fix a target function \(f : X \to Y \to \alpha \), real parameters \(\varepsilon \) and \(c\) with \(c \gt 1\), and suppose that \(p\) \(\varepsilon \)-computes \(f\). Then the communication complexity of the associated Newman protocol equals
where \(t(X, Y, \varepsilon , c)\) is the derandomization sample count and \(\mathrm{complexity}(p)\) is the communication complexity of \(p\); that is, running the Newman protocol costs exactly the cost of \(p\) together with the number of bits Alice needs to name one seed in the table of size \(t(X, Y, \varepsilon , c)\).
Let \(X\) and \(Y\) be finite types, let \(f : X \to Y \to \alpha \), and let \(\varepsilon , \varepsilon ', c \in \mathbb {R}\) satisfy \(1 \lt c\) and \(c\varepsilon \lt \varepsilon '\). Then the private-coin communication complexity of \(f\) at error tolerance \(\varepsilon '\) does not exceed the public-coin communication complexity of \(f\) at error tolerance \(\varepsilon \) increased by \(\lceil \log _2 t(X, Y, \varepsilon , c)\rceil \), where \(t(X, Y, \varepsilon , c)\) is the derandomization sample count; that is,
with both complexities taken as values in \(\mathbb {N}\cup \{ \infty \} \).