86 Communication Complexity — Discrepancy
86.1 Overview
This module establishes the discrepancy method lower bound for public-coin communication complexity. The central definition is the discrepancy of a Boolean function \(g : X \to Y \to \mathrm{Bool}\) on a combinatorial rectangle \(R \subseteq X \times Y\) with respect to a distribution \(\mu \); the main result is that if every rectangle has discrepancy at most \(\gamma \), then the (public-coin) communication complexity of \(g\) must be large.
86.2 Declarations
Let \(\mu \) be a finite probability space on \(X \times Y\), let \(g : X \to Y \to \mathrm{Bool}\), and let \(S \subseteq X \times Y\). The discrepancy of \(g\) on \(S\) with respect to \(\mu \) is
where \(\sigma : \mathrm{Bool} \to \{ -1,1\} \) is the sign map CommunicationComplexity.boolSign.
For any \(g : X \to Y \to \mathrm{Bool}\), \(S \subseteq X \times Y\), and point \((x,y) \in X \times Y\), the pointwise integrand \(\mathbf{1}_{S}(x,y)\cdot \sigma (g(x,y))\) equals the indicator of \(\{ (x,y)\in S \mid g(x,y)=\mathrm{false}\} \) minus the indicator of \(\{ (x,y)\in S \mid g(x,y)=\mathrm{true}\} \) evaluated at \((x,y)\).
The discrepancy of \(g\) on \(S\) equals the \(\mu \)-probability mass of the set where \(g\) outputs \(\mathrm{false}\) inside \(S\), minus the \(\mu \)-probability mass of the set where \(g\) outputs \(\mathrm{true}\) inside \(S\):
If every combinatorial rectangle \(R \subseteq X \times Y\) satisfies \(|\mathrm{disc}_\mu (g,R)| \le \gamma \), then \(\gamma \ge 0\).
For a deterministic Boolean protocol \(p\) and a set \(R \subseteq X \times Y\), the rectangle sign is \(+1\) if the protocol outputs \(\mathrm{false}\) on every point of \(R\), and \(-1\) otherwise.
For any protocol \(p\) and any set \(R\), \(|\mathrm{rectangleSign}(p,R)| = 1\).
If \(R\) is a leaf rectangle of protocol \(p\) and \((x,y) \in R\), then \(\mathrm{rectangleSign}(p,R) = \sigma (p.\mathrm{run}(x,y))\), where \(\sigma \) is the sign map CommunicationComplexity.boolSign.
Given a finite probability space \(\mu \) on \(X \times Y\) and a deterministic protocol \(p\), this is the canonical Finset enumerating the (finitely many) leaf rectangles of \(p\).
A set \(R\) belongs to CommunicationComplexity.Deterministic.Protocol.leafRectanglesFinset \(p\) if and only if it is a leaf rectangle of \(p\).
For every point \((x,y) \in X \times Y\), the sum over all leaf rectangles \(R\) of \(\mathbf{1}_{R}(x,y) \cdot \mathrm{rectangleSign}(p,R)\) equals \(\sigma (p.\mathrm{run}(x,y))\). This uses the fact that the leaf rectangles form a partition of \(X \times Y\).
For a deterministic protocol \(p\) and Boolean function \(g\),
The signed bias \(\mathbb {E}_{(x,y)}\bigl[\sigma (p.\mathrm{run}(x,y))\cdot \sigma (g(x,y))\bigr]\) equals the sum over all leaf rectangles \(R\) of \(\mathrm{rectangleSign}(p,R)\cdot \mathrm{disc}_\mu (g,R)\).
If every combinatorial rectangle \(R\) satisfies \(|\mathrm{disc}_\mu (g,R)| \le \gamma \), then for any deterministic protocol \(p\),
Assuming \(\gamma \gt 0\) and \(1 - 2 \cdot p.\mathrm{distributionalError}_\mu (g) \gt 0\), if every rectangle has discrepancy at most \(\gamma \) then
Let \(\mu \) be a distribution on \(X \times Y\), let \(g : X \to Y \to \mathrm{Bool}\), and let \(\varepsilon , \gamma \in \mathbb {R}\) and \(n \in \mathbb {N}\). If every combinatorial rectangle \(R\) satisfies \(|\mathrm{disc}_\mu (g,R)| \le \gamma \), and if \(2^n \cdot \gamma \lt 1 - 2\varepsilon \), then \(n \lt \mathrm{CC}(g,\varepsilon )\) (the public-coin \(\varepsilon \)-error communication complexity of \(g\)).