45 Communication Complexity — Func Disjointness
45.1 Overview
This module establishes the exact deterministic communication complexity of the set-disjointness function on subsets of \([n]\). Using a fooling-set argument based on the pairs \((X, X^c)\), it shows that for \(n \ge 1\) the complexity is exactly \(n + 1\).
45.2 Declarations
For \(n \in \mathbb {N}\) and subsets \(X, Y \subseteq [n]\), \(\mathrm{disjointness}(n, X, Y)\) is the Boolean function that returns \(\mathtt{true}\) if and only if \(X\) and \(Y\) are disjoint, i.e. \(X \cap Y = \emptyset \).
For every \(n \in \mathbb {N}\) and all subsets \(X, Y \subseteq [n]\), the disjointness function is symmetric in its two arguments: \(\mathrm{disjointness}(n, X, Y) = \mathrm{disjointness}(n, Y, X)\). That is, since \(X\) and \(Y\) are disjoint if and only if \(Y\) and \(X\) are disjoint, swapping the two sets leaves the Boolean value unchanged.
The candidate fooling set for disjointness is the collection of all pairs \((X, X^c)\) where \(X \subseteq [n]\), i.e. \(\mathrm{foolingSet}(n) = \{ (X, Y) \mid Y = X^c\} \).
Fix \(n \in \mathbb {N}\), and consider the set-disjointness function on subsets of \([n]\), namely the Boolean function \(g(X, Y)\) that is \(\mathtt{true}\) exactly when \(X \cap Y = \emptyset \). Then the collection \(\{ (X, X^c) \mid X \subseteq [n]\} \) of complementary pairs is a fooling set for \(g\): for every rectangle \(R = A \times B\) (with \(A, B\) families of subsets of \([n]\)) that is monochromatic for \(g\), the intersection of \(R\) with this collection contains at most one point.
For every \(n \in \mathbb {N}\), the fooling set for disjointness — the collection of all pairs \((X, X^c)\) with \(X \subseteq [n]\) — has exactly \(2^n\) elements.
Fix \(n \in \mathbb {N}\), and let both players’ inputs range over subsets of \([n] = \{ 0, 1, \dots , n-1\} \), so that Alice holds \(X \subseteq [n]\) and Bob holds \(Y \subseteq [n]\). The deterministic communication complexity of the set-disjointness function, which returns \(\mathtt{true}\) exactly when \(X \cap Y = \emptyset \), is at most \(n + 1\).
Fix an integer \(n \ge 1\), and consider the set-disjointness function on subsets of \([n]\): it takes a pair of subsets \(X, Y \subseteq [n]\) — Alice holding \(X\) and Bob holding \(Y\) — to \(\mathtt{true}\) exactly when \(X \cap Y = \emptyset \). Then the deterministic communication complexity of this function is at least \(n + 1\).
Let \(n \geq 1\), and let \(\mathrm{disjointness}(n, \cdot , \cdot )\) denote the two-party Boolean function that, given subsets \(X, Y \subseteq [n]\) held by Alice and Bob respectively, returns \(\mathtt{true}\) exactly when \(X \cap Y = \emptyset \). Then the deterministic communication complexity of this function is exactly \(n + 1\).
45.3 Additional declarations
The ceiling base-\(2\) logarithm of \(2\) equals \(1\): \(\lceil \log _2 2 \rceil = 1\), i.e. \(\texttt{Nat.clog}\, 2\, 2 = 1\). This is a small numerical fact used in the communication-complexity bounds of this module.