84 Communication Complexity — Newman Theorem
84.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.
84.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.
If \(p\) is a public-coin finite-message protocol that \(\varepsilon \)-computes \(f\), and \(c \gt 1\), then the Newman protocol \((p.\mathtt{newmanProtocol}\; f\; \varepsilon \; c)\) is a private-coin protocol that \((c \cdot \varepsilon )\)-computes \(f\), i.e. for all inputs \(x \in X\) and \(y \in Y\) the probability that the protocol’s output differs from \(f(x, y)\) is at most \(c \cdot \varepsilon \).
If \(p\) is a public-coin finite-message protocol that \(\varepsilon \)-computes \(f\), and \(c \gt 1\), then the communication complexity of the Newman protocol equals \(\lceil \log _2(\mathtt{derandomizationSamples}\; X\; Y\; \varepsilon \; c) \rceil + p.\mathtt{complexity}\), i.e. the original complexity plus the number of bits needed to index the seed table.
Let \(f : X \to Y \to \alpha \) with \(X, Y\) finite, let \(\varepsilon , \varepsilon ' \in \mathbb {R}\) and \(c \gt 1\) satisfy \(c \cdot \varepsilon \lt \varepsilon '\). Then the private-coin communication complexity of \(f\) at error \(\varepsilon '\) is at most the public-coin complexity at error \(\varepsilon \) plus \(\lceil \log _2(\mathtt{derandomizationSamples}\; X\; Y\; \varepsilon \; c) \rceil \):
In particular, switching from public-coin to private-coin randomness costs only \(O(\log (|X| \cdot |Y|) / \varepsilon ^2)\) additional bits.