43 Communication Complexity — Det Rectangle
43.1 Overview
This module establishes that every deterministic communication protocol induces a monochromatic rectangle partition of the input space \(X \times Y\) into at most \(2^c\) rectangles, where \(c\) is the protocol’s communication complexity. It also derives the fooling-set lower-bound method, showing that the size of any fooling set bounds \(\mathrm{CC}(g)\) from below via \(\lceil \log _2 |S| \rceil \leq \mathrm{CC}(g)\).
43.2 Declarations
Given a set \(R \subseteq X \times Y\), \(\texttt{swapInputSet}(R)\) is the set \(\{ (y, x) \mid (x, y) \in R\} \subseteq Y \times X\) obtained by swapping the two coordinates of every element.
Let \(R \subseteq X \times Y\), and write \(\mathrm{swap}(R) = \{ (y,x) \mid (x,y) \in R\} \subseteq Y \times X\) for the set obtained by exchanging the two coordinates of every element of \(R\). Then for any pair \((y, x) \in Y \times X\), one has \((y, x) \in \mathrm{swap}(R)\) if and only if \((x, y) \in R\).
For any set \(R \subseteq X \times Y\), swapping the two coordinates of every element twice returns the original set: writing \(\mathrm{swap}(R) = \{ (y,x) \mid (x,y) \in R\} \), one has \(\mathrm{swap}(\mathrm{swap}(R)) = R\).
Given maps \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) and a set \(R \subseteq X \times Y\), \(\texttt{preimageInputSet}(f_X, f_Y, R)\) is the set \(\{ (x', y') \in X' \times Y' \mid (f_X(x'), f_Y(y')) \in R\} \), the pullback of \(R\) along the product map \(f_X \times f_Y\).
Let \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) be maps, let \(R \subseteq X \times Y\), and let \((x', y') \in X' \times Y'\). Then \((x', y')\) lies in the pullback of \(R\) along the product map \(f_X \times f_Y\) if and only if \((f_X(x'), f_Y(y')) \in R\).
For a protocol \(p\) and sets \(A \subseteq X\), \(B \subseteq Y\), \(\texttt{leafRectanglesAux}(p, A, B)\) is the collection of rectangles induced by the leaves of \(p\) when the reachable inputs are constrained to \(A \times B\). It is defined by structural recursion: an output node yields \(\{ A \times B\} \), while Alice (resp. Bob) nodes split \(A\) (resp. \(B\)) according to the branching function and recurse.
The leaf rectangles of a protocol \(p : \texttt{Protocol}\, X\, Y\, \alpha \) form the collection \(\texttt{leafRectangles}(p) = \texttt{leafRectanglesAux}(p, X, Y)\), i.e. the set of input rectangles induced by the leaves of \(p\) over the full input space \(X \times Y\).
Let \(p\) be a deterministic communication protocol over input types \(X\) (Alice) and \(Y\) (Bob), and let \(A \subseteq X\) and \(B \subseteq Y\). Denote by \(p^{\mathrm{sw}}\) the role-swapped protocol over \(Y \times X\) obtained by exchanging Alice and Bob throughout, and for a set \(R \subseteq X \times Y\) write \(R^{\mathrm{sw}} = \{ (y,x) \mid (x,y) \in R\} \subseteq Y \times X\) for its coordinate swap. Then for every rectangle \(R\) in the collection of auxiliary leaf rectangles of \(p\) relative to \(A \times B\), the swapped set \(R^{\mathrm{sw}}\) belongs to the collection of auxiliary leaf rectangles of \(p^{\mathrm{sw}}\) relative to \(B \times A\).
Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob), and let \(p^{\mathrm{swap}}\) be the protocol over \(Y \times X\) obtained by exchanging the roles of Alice and Bob throughout. If \(R \subseteq X \times Y\) is one of the leaf rectangles of \(p\), then its coordinate swap \(\{ (y,x) \mid (x,y) \in R\} \subseteq Y \times X\) is one of the leaf rectangles of \(p^{\mathrm{swap}}\).
Let \(p\) be a deterministic communication protocol over input types \(X\) and \(Y\), let \(A \subseteq X\) and \(B \subseteq Y\), and let \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) be arbitrary maps. If \(R \subseteq X \times Y\) is one of the leaf rectangles of \(p\) relative to the constraint \(A \times B\), then its pullback along \(f_X \times f_Y\), namely \(\{ (x', y') \in X' \times Y' \mid (f_X(x'), f_Y(y')) \in R\} \), is one of the leaf rectangles of the pulled-back protocol \(\mathrm{comap}(p, f_X, f_Y)\) relative to the constraint \(f_X^{-1}(A) \times f_Y^{-1}(B)\).
Let \(p\) be a deterministic communication protocol over input types \(X\) and \(Y\) producing values in \(\alpha \), and let \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) be arbitrary maps. Write \(p'\) for the protocol over \(X' \times Y'\) obtained from \(p\) by pre-composing every message function with \(f_X\) or \(f_Y\) as appropriate. If \(R \subseteq X \times Y\) is a leaf rectangle of \(p\), then its pullback \(\{ (x', y') \in X' \times Y' \mid (f_X(x'), f_Y(y')) \in R\} \) along the product map \(f_X \times f_Y\) is a leaf rectangle of \(p'\).
Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob), and let \(A \subseteq X\) and \(B \subseteq Y\). Then every set belonging to the auxiliary leaf-rectangle collection of \(p\) relative to the constraint \(A \times B\) is a rectangle; that is, if \(R \subseteq X \times Y\) is one of these leaf sets, then \(R = A' \times B'\) for some \(A' \subseteq X\) and \(B' \subseteq Y\).
Let \(p\) be a deterministic two-party communication protocol with Alice’s inputs drawn from \(X\) and Bob’s from \(Y\), and let \(R\) belong to the collection of leaf rectangles of \(p\) over the full input space \(X \times Y\). Then \(R\) is a rectangle: there exist subsets \(A \subseteq X\) and \(B \subseteq Y\) with \(R = A \times B\).
Let \(p\) be a deterministic two-party communication protocol over input types \(X\) (Alice) and \(Y\) (Bob), and let \(A \subseteq X\) and \(B \subseteq Y\). Then every rectangle \(R\) in the collection of auxiliary leaf rectangles of \(p\) constrained to \(A \times B\) satisfies \(R \subseteq A \times B\).
Let \(p\) be a deterministic two-party communication protocol with Alice’s inputs drawn from a set \(X\), Bob’s inputs from a set \(Y\), and outputs in a type \(\alpha \), and let \(A \subseteq X\) and \(B \subseteq Y\). Then the rectangle \(A \times B\) is contained in the union of the auxiliary leaf rectangles of \(p\) relative to the constraint \(A \times B\); that is, every pair \((x, y) \in A \times B\) lies in at least one rectangle of this collection.
Let \(p\) be a deterministic communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) producing values of type \(\alpha \), and let \(A \subseteq X\) and \(B \subseteq Y\). If \(R\) and \(S\) are two distinct rectangles in the collection of auxiliary leaf rectangles of \(p\) relative to \(A\) and \(B\), then \(R\) and \(S\) are disjoint as subsets of \(X \times Y\).
Let \(p\) be a deterministic communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) producing a value of some type \(\alpha \). Then the leaf rectangles of \(p\) cover the entire input space: the union of all rectangles in the collection of leaf rectangles of \(p\) equals \(X \times Y\).
Let \(p\) be a deterministic two-party communication protocol over input types \(X\) and \(Y\) producing values in \(\alpha \), and let \(R\) and \(S\) be two of its leaf rectangles, that is, two of the input rectangles induced by the leaves of \(p\) over \(X \times Y\). If \(R \neq S\), then \(R\) and \(S\) are disjoint as subsets of \(X \times Y\).
Let \(p\) be a deterministic communication protocol over input types \(X\) (Alice) and \(Y\) (Bob) with outputs in \(\alpha \), and let \(A \subseteq X\) and \(B \subseteq Y\). If \(R\) is one of the auxiliary leaf rectangles of \(p\) constrained to \(A \times B\), and \((x, y)\) and \((x', y')\) both belong to \(R\), then running \(p\) yields the same output at both inputs; that is, \(p(x, y) = p(x', y')\).
Let \(p\) be a deterministic two-party communication protocol over input types \(X\) and \(Y\) with output type \(\alpha \), and let \(g : X \to Y \to \alpha \) be a function that \(p\) computes, meaning that running \(p\) on any pair of inputs \((x, y)\) returns \(g\, x\, y\). Then every leaf rectangle \(R\) of \(p\) is monochromatic for \(g\): the value \(g\, x\, y\) is the same for all \((x, y) \in R\).
Let \(p\) be a deterministic two-party communication protocol with input types \(X\) (Alice) and \(Y\) (Bob), and let \(A \subseteq X\) and \(B \subseteq Y\). Then the number of distinct rectangles among the auxiliary leaf rectangles of \(p\) relative to the constraint \(A \times B\) is at most \(2^{c}\), where \(c\) is the communication complexity of \(p\).
Let \(X\), \(Y\), and \(\alpha \) be types, let \(p\) be a deterministic two-party communication protocol over inputs \(X\) (Alice) and \(Y\) (Bob) with outputs in \(\alpha \), and let \(A \subseteq X\) and \(B \subseteq Y\). Then the collection of leaf rectangles induced by \(p\) when its reachable inputs are constrained to \(A \times B\) is finite.
Let \(p\) be a deterministic two-party communication protocol over input types \(X\) and \(Y\) producing values in \(\alpha \), and let \(c\) be its communication complexity. Then the number of leaf rectangles of \(p\) is at most \(2^{c}\).
For any deterministic two-party communication protocol \(p\) over input types \(X\) (Alice) and \(Y\) (Bob) producing values in \(\alpha \), the collection of leaf rectangles of \(p\) — the input rectangles in \(X \times Y\) induced by the leaves of \(p\) over the full input space — is finite.
Let \(p\) be a deterministic two-party communication protocol over input types \(X\) and \(Y\) producing outputs in \(\alpha \), and let \(g : X \to Y \to \alpha \). If \(p\) computes \(g\), then the collection of leaf rectangles of \(p\) is a monochromatic rectangle partition of \(X \times Y\) for \(g\): every leaf rectangle is a rectangle and is monochromatic for \(g\), the leaf rectangles cover all of \(X \times Y\), and any two distinct leaf rectangles are disjoint.
Let \(p\) be a deterministic two-party communication protocol on input types \(X\) and \(Y\) with output type \(\alpha \), and let \(g : X \to Y \to \alpha \) be a function that \(p\) computes. Then the leaf rectangles of \(p\) form a monochromatic rectangle partition of \(X \times Y\) for \(g\); that is, they are pairwise disjoint rectangles covering \(X \times Y\), each of which is monochromatic for \(g\). Moreover, the number of leaf rectangles is at most \(2^{c}\), where \(c\) is the communication complexity of \(p\).
Let \(s\) and \(p\) be deterministic two-party communication protocols over Alice’s input type \(X\) and Bob’s input type \(Y\), and let \(\pi \) be a subprotocol path witnessing that \(s\) is a rooted subtree of \(p\). Then the set of input pairs
is a rectangle. Explicitly, it factors as \(A \times B\), where \(A \subseteq X\) is the set of Alice inputs consistent with every one of Alice’s branching choices along \(\pi \) and \(B \subseteq Y\) is the set of Bob inputs consistent with every one of Bob’s branching choices along \(\pi \).
Let \(X\), \(Y\), and \(\alpha \) be types, let \(p\) be a deterministic two-party communication protocol over Alice’s inputs \(X\) and Bob’s inputs \(Y\) with outputs in \(\alpha \), and suppose \(s\) is a rooted subtree of \(p\). Then the set of input pairs \((x, y) \in X \times Y\) that reach \(s\) — those for which \(x\) lies in Alice’s reach set and \(y\) lies in Bob’s reach set — is a rectangle: it factors as a product \(A \times B\) for some \(A \subseteq X\) and \(B \subseteq Y\).
Let \(g : X \times Y \to \alpha \) be a two-argument function, and let \(n\) be a natural number. If the deterministic communication complexity \(D(g)\) satisfies \(D(g) \le n\), then there is a collection \(\mathcal{P}\) of subsets of \(X \times Y\) that is a monochromatic rectangle partition for \(g\) — every member is a rectangle, every member is monochromatic for \(g\), the members cover \(X \times Y\), and distinct members are disjoint — and whose number of parts satisfies \(\left\lvert \mathcal{P}\right\rvert \le 2^n\).
Let \(g : X \to Y \to \alpha \) be a two-argument function and let \(n\) be a natural number. If every monochromatic rectangle partition of \(g\) consists of strictly more than \(2^n\) parts, then the deterministic communication complexity of \(g\) satisfies \(n + 1 \le D(g)\).
Let \(g : X \times Y \to \alpha \) be a two-argument function, and let \(S \subseteq X \times Y\) be a fooling set for \(g\), meaning that \(S\) meets every \(g\)-monochromatic rectangle in at most one point. If the deterministic communication complexity of \(g\) satisfies \(D(g) \le n\) for some \(n \in \mathbb {N}\), then the cardinality of \(S\) satisfies \(\left\lvert S\right\rvert \le 2^{n}\).
Let \(g : X \times Y \to \alpha \) be a two-argument function and let \(S \subseteq X \times Y\) be a fooling set for \(g\), meaning that every rectangle that is monochromatic for \(g\) meets \(S\) in at most one point. Then the deterministic communication complexity of \(g\) satisfies
where \(\left\lvert S\right\rvert \) is the number of elements of \(S\) and both sides are compared in \(\mathbb {N}_\infty \).
43.3 Additional declarations
Let \(p\) be a protocol on \(X \times Y\), let \(A \subseteq X\), \(B \subseteq Y\), let \(f : X \to \{ 0,1\} \) be the bit Alice sends, and let \(b\) be a bit. If \(R\) is a leaf rectangle of \(p\) run on the restricted input set \((A \cap \{ x \mid f(x) = b\} ) \times B\), then every input \((x, y) \in R\) satisfies \(f(x) = b\).
Let \(p\) be a protocol on \(X \times Y\), let \(A \subseteq X\), \(B \subseteq Y\), let \(f : Y \to \{ 0,1\} \) be the bit Bob sends, and let \(b\) be a bit. If \(R\) is a leaf rectangle of \(p\) run on the restricted input set \(A \times (B \cap \{ y \mid f(y) = b\} )\), then every input \((x, y) \in R\) satisfies \(f(y) = b\). This is the mirror image of CommunicationComplexity.Deterministic.Protocol.aux_alice_bit.
Let \(p, q\) be protocols on \(X \times Y\), let \(A \subseteq X\), \(B \subseteq Y\), let \(f : X \to \{ 0,1\} \), and let \(b \neq b'\) be distinct bits. If \(R\) is a leaf rectangle of \(p\) on \((A \cap \{ x \mid f(x) = b\} ) \times B\) and \(S\) is a leaf rectangle of \(q\) on \((A \cap \{ x \mid f(x) = b'\} ) \times B\), then \(R\) and \(S\) are disjoint.
Let \(p, q\) be protocols on \(X \times Y\), let \(A \subseteq X\), \(B \subseteq Y\), let \(f : Y \to \{ 0,1\} \), and let \(b \neq b'\) be distinct bits. If \(R\) is a leaf rectangle of \(p\) on \(A \times (B \cap \{ y \mid f(y) = b\} )\) and \(S\) is a leaf rectangle of \(q\) on \(A \times (B \cap \{ y \mid f(y) = b'\} )\), then \(R\) and \(S\) are disjoint. This is the mirror image of CommunicationComplexity.Deterministic.Protocol.aux_disjoint_alice_of_ne.
Let \(S_0, S_1\) be sets in a type \(\beta \) and let \(c_0, c_1 \in \mathbb {N}\). If \(\left\lvert S_0\right\rvert \le 2^{c_0}\) and \(\left\lvert S_1\right\rvert \le 2^{c_1}\), then
where \(\left\lvert \cdot \right\rvert \) denotes the number of elements of a set.