85 Communication Complexity — Derandomization
85.1 Overview
This module establishes the Chernoff-plus-union-bound derandomization step at the heart of Newman’s theorem. Starting from a public-coin protocol that \(\varepsilon \)-computes a function \(f : X \times Y \to \alpha \), it produces \(t = O\! \left(\log (|X|\cdot |Y|)/((c-1)^2\varepsilon ^2)\right)\) explicit random seeds that collectively cover every input: for every \((x,y)\), at most a \(c\varepsilon \) fraction of the seeds cause an incorrect output.
85.2 Declarations
Let \((\Omega ', \mu )\) be a probability space and let \(Y_0, \dots , Y_{t-1} : \Omega ' \to \mathbb {R}\) be mutually independent, a.e. \([0,1]\)-valued random variables satisfying \(\mathbb {E}[Y_i] \le \varepsilon \) for all \(i\), with \(\varepsilon \ge 0\) and \(c \gt 1\). Then
Given finite types \(X\) and \(Y\) and real parameters \(\varepsilon , c\), the number of random samples required for derandomization via Chernoff and union bound is
where \(\lceil \cdot \rceil _{+}\) denotes the natural-number ceiling.
Let \(\Omega \) be a finite probability space, let \(p\) be a public-coin protocol on \(X \times Y\) with output type \(\alpha \), and let \(f : X \to Y \to \alpha \). Suppose \(c \gt 1\) and \(p\) \(\varepsilon \)-computes \(f\) (i.e. for every \((x, y)\), the probability that \(p\) produces an incorrect output is at most \(\varepsilon \)). Then there exist \(t = \texttt{CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.derandomizationSamples}(X, Y, \varepsilon , c)\) random seeds \(\omega _0, \dots , \omega _{t-1} \in \Omega \) such that for every \((x, y)\),