48 Communication Complexity — Func Disjointness
48.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\).
48.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 \).
The disjointness function is symmetric in its two set arguments: for all \(X, Y \subseteq [n]\), \(\mathrm{disjointness}(n, X, Y) = \mathrm{disjointness}(n, Y, X)\).
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\} \).
The collection \(\{ (X, X^c) \mid X \subseteq [n]\} \) is a fooling set for \(\mathrm{disjointness}(n)\): every pair \((X, X^c)\) evaluates to \(\mathtt{true}\), and for any monochromatic rectangle \(R\) with \(\mathrm{disjointness} = \mathtt{true}\) that contains two distinct fooling-set pairs, those pairs must coincide.
The fooling set \(\mathrm{foolingSet}(n)\) has cardinality \(2^n\), since it is in bijection with the power set of \([n]\) via \(X \mapsto (X, X^c)\).
The deterministic communication complexity of \(\mathrm{disjointness}(n)\) is at most \(n + 1\): Alice can communicate her entire set \(X \subseteq [n]\) in \(n\) bits, after which Bob sends a single bit for the answer.
For \(n \ge 1\), the deterministic communication complexity of \(\mathrm{disjointness}(n)\) is at least \(n + 1\). The proof uses the fooling set of size \(2^n\) together with an additional input \((x_0, y_0)\) with \(x_0 \cap y_0 \ne \emptyset \) to show that any monochromatic partition of the input space into rectangles requires more than \(2^n\) pieces.
For \(n \ge 1\), the deterministic communication complexity of the set-disjointness function on subsets of \([n]\) is exactly \(n + 1\). This follows by combining the matching upper and lower bounds.