81 Communication Complexity — Func Equality
81.1 Overview
This module establishes the exact deterministic communication complexity of the equality function on \(n\)-bit strings and provides a public-coin upper bound via universal hashing. The two headline results are: the deterministic complexity equals \(0\) when \(n = 0\) and \(n + 1\) otherwise; and the public-coin complexity is at most \(\lceil \log _2(\lceil \varepsilon ^{-1} \rceil + 1)\rceil + 1\) for any error tolerance \(\varepsilon \gt 0\).
81.2 Declarations
For a natural number \(n\), CommunicationComplexity.Functions.Equality.equality is the Boolean function \(\mathrm{equality}_n : \mathrm{BoolInput}\, n \times \mathrm{BoolInput}\, n \to \mathrm{Bool}\) that returns true if and only if Alice’s input \(x\) equals Bob’s input \(y\).
\(\mathrm{HashSpace}(n, k)\) is the type of all hash functions from \(n\)-bit strings into \(\mathrm{Fin}(2^k)\); it serves as the public-randomness space for the hashing-based equality protocol.
For every \(n \in \mathbb {N}\),
This follows from the naive protocol in which Alice transmits her entire \(n\)-bit input and Bob sends back the single comparison bit.
When \(n = 0\) both inputs are the unique empty string, so the equality function is constantly true and requires zero communication:
For every \(n \ge 1\),
The key argument is that any monochromatic rectangle that contains a diagonal pair \((x, x)\) must equal the singleton \(\{ (x,x)\} \), so any valid partition of the input matrix into monochromatic rectangles contains at least \(2^n + 1\) pieces, requiring \(n + 1\) bits to index.
The deterministic communication complexity of the equality function on \(n\)-bit strings is
\(\mathrm{equalityHashProtocol}(n, k)\) is the standard public-coin protocol for equality in which, given a shared random hash \(h \in \mathrm{HashSpace}(n, k)\), Alice sends \(h(x) \in \mathrm{Fin}(2^k)\) and Bob replies with \(\mathtt{decide}(h(y) = h(x))\).
For all \(x, y : \mathrm{BoolInput}\, n\) and \(h : \mathrm{HashSpace}(n,k)\),
The worst-case communication cost of \(\mathrm{equalityHashProtocol}(n, k)\) is exactly \(k + 1\) bits.
If \(\varepsilon \gt 0\) and \(1/2^k \lt \varepsilon \), then the public-coin communication complexity of \(\mathrm{equality}_n\) with error at most \(\varepsilon \) satisfies
The error bound follows from the collision probability of the random hash family.
For every \(n \in \mathbb {N}\) and every \(\varepsilon \gt 0\),