78 Communication Complexity — Func Equality

78.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\).

78.2 Declarations

Definition 78.1 Equality function on \(n\)-bit strings

✓

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\).

Definition 78.2 Hash space for the equality protocol

✓

\(\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.

Theorem 78.3 Deterministic complexity upper bound for equality

✓

For every natural number \(n\), the deterministic communication complexity of the \(n\)-bit equality function satisfies

\[ D(\mathrm{equality}_n) \; \le \; n+1, \]

where \(\mathrm{equality}_n : \mathrm{BoolInput}\, n \times \mathrm{BoolInput}\, n \to \mathrm{Bool}\) is the function that returns \(\mathtt{true}\) exactly when Alice’s input equals Bob’s, and the bound is an inequality in \(\mathbb {N}_\infty \).

Theorem 78.4 Deterministic complexity of equality at \(n = 0\)

✓

Let \(\mathrm{equality}_0 \colon \mathrm{BoolInput}\, 0 \times \mathrm{BoolInput}\, 0 \to \mathrm{Bool}\) be the equality function on \(0\)-bit Boolean inputs, and let \(D(\mathrm{equality}_0)\) denote its deterministic communication complexity, that is, the infimum over all deterministic two-party protocols computing it of the worst-case number of bits exchanged, taken in \(\mathbb {N}_\infty \). Then

\[ D(\mathrm{equality}_0) = 0. \]

Theorem 78.5 Deterministic complexity lower bound for equality

✓

For every natural number \(n \ge 1\), the deterministic communication complexity of the \(n\)-bit equality function satisfies

\[ n + 1 \; \le \; D(\mathrm{equality}_n), \]

where \(\mathrm{equality}_n\) is the Boolean function on \(\mathrm{BoolInput}\, n \times \mathrm{BoolInput}\, n\) that returns \(\mathtt{true}\) exactly when Alice’s input equals Bob’s input.

Theorem 78.6 Exact deterministic complexity of equality

✓

For a natural number \(n\), let \(\mathrm{equality}_n\) denote the two-party Boolean function on \(n\)-bit strings that returns \(\mathtt{true}\) precisely when Alice’s input \(x \in \mathrm{BoolInput}(n)\) equals Bob’s input \(y \in \mathrm{BoolInput}(n)\). Its deterministic communication complexity, measured in \(\mathbb {N}_\infty \) as the least worst-case number of bits exchanged by any deterministic protocol computing it, is

\[ D(\mathrm{equality}_n) \; =\; \begin{cases} 0 & \text{if } n = 0,\\ n + 1 & \text{otherwise.} \end{cases} \]

Definition 78.7 Equality hashing protocol

✓

\(\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))\).

Theorem 78.8 Output of the equality hashing protocol

✓

Fix natural numbers \(n\) and \(k\), let \(x, y \in \mathrm{BoolInput}(n)\) be \(n\)-bit Boolean strings, and let \(h \in \mathrm{HashSpace}(n,k)\) be a hash function sending \(n\)-bit strings into \(\mathrm{Fin}(2^k)\). Running the equality hashing protocol on private inputs \(x\) and \(y\) with \(h\) as the shared public randomness returns the Boolean value \(\mathrm{decide}(h(x) = h(y))\); that is, the protocol outputs \(\mathrm{true}\) precisely when the two hashes \(h(x)\) and \(h(y)\) agree.

Theorem 78.9 Communication cost of the equality hashing protocol

✓

For all natural numbers \(n\) and \(k\), the public-coin equality hashing protocol on \(n\)-bit Boolean inputs with hash range \(\mathrm{Fin}(2^k)\) — in which, given a shared random hash \(h\), Alice sends the value \(h(x) \in \mathrm{Fin}(2^k)\) and Bob replies with the truth value of whether \(h(y) = h(x)\) — has worst-case communication complexity exactly \(k + 1\) bits.

Theorem 78.10 Public-coin upper bound for equality by hashing

✓

Fix natural numbers \(n\) and \(k\) and a real number \(\varepsilon \) satisfying \(1/2^{k} \lt \varepsilon \). Then the \(\varepsilon \)-error public-coin randomized communication complexity of the equality function \(\mathrm{equality}_n\) on pairs of \(n\)-bit Boolean strings satisfies

\[ \mathrm{R}^{\mathrm{pub}}_{\varepsilon }(\mathrm{equality}_n) \; \le \; k + 1, \]

where the bound is taken in the extended naturals \(\mathbb {N}\cup \{ \infty \} \).

Theorem 78.11 Public-coin communication complexity of equality

✓

For every natural number \(n\) and every real \(\varepsilon \gt 0\), the \(\varepsilon \)-error public-coin randomized communication complexity of the equality function \(\mathrm{equality}_n\) on pairs of \(n\)-bit Boolean strings satisfies

\[ \mathrm{R}^{\mathrm{pub}}_\varepsilon (\mathrm{equality}_n) \; \le \; \left\lceil \log _2\! \left(\lceil \varepsilon ^{-1}\rceil + 1\right)\right\rceil + 1, \]

where \(\lceil \varepsilon ^{-1}\rceil \) denotes the least natural number at least \(\varepsilon ^{-1}\) and \(\lceil \, \cdot \, \rceil \) inside the logarithm the ceiling of the base-\(2\) logarithm. That is, there is a public-coin protocol computing \(\mathrm{equality}_n\) with error probability at most \(\varepsilon \) on every input pair whose worst-case number of exchanged bits is bounded by this quantity.

78.3 Additional declarations

Theorem 78.12 Ceiling logarithm of \(2\) in base \(2\)

✓

The base-\(2\) ceiling logarithm of \(2\) equals \(1\): \(\lceil \log _2 2 \rceil = 1\), i.e. Nat.clog 2 2 = 1. This is a small arithmetic fact used in the deterministic upper bound for the equality function.