82 Communication Complexity — Derandomization
82.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.
82.2 Declarations
Let \((\Omega ', \mu )\) be a probability space, let \(t \ge 1\), and let \(Y_0, \dots , Y_{t-1} : \Omega ' \to \mathbb {R}\) be mutually independent, almost everywhere measurable random variables that almost surely take values in \([0,1]\). Suppose \(\mathbb {E}[Y_i] \le \varepsilon \) for every \(i\), where \(0 \le \varepsilon \), and let \(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 and let \(X\) and \(Y\) be finite input sets. Let \(p\) be a public-coin finite-message protocol over shared randomness \(\Omega \) with private inputs in \(X\) and \(Y\) and output type \(\alpha \), let \(f : X \to Y \to \alpha \), and let \(\varepsilon , c \in \mathbb {R}\) with \(c \gt 1\). Suppose \(p\) \(\varepsilon \)-computes \(f\), so that for every input pair \((x,y)\) the probability over \(\omega \) that the randomized execution \(\mathrm{rrun}(p,x,y,\omega )\) differs from \(f(x,y)\) is at most \(\varepsilon \). Then, writing \(t = t(X,Y,\varepsilon ,c)\) for the derandomization sample count, there exists a family \(\omega _0, \dots , \omega _{t-1} \in \Omega \) of shared-randomness values such that for every \((x,y)\),