83 Communication Complexity — Rank
83.1 Overview
This module establishes the log-rank lower bound for deterministic communication complexity. Given a Boolean function \(f : X \to Y \to \{ 0,1\} \), one forms its real-valued \(0/1\) matrix \(M_f\) and shows that the deterministic communication complexity of \(f\) is at least \(\lceil \log _2 \mathrm{rank}(M_f) \rceil \).
83.2 Declarations
Given a Boolean function \(f : X \to Y \to \mathrm{Bool}\), the matrix \(M_f \in \mathbb {R}^{X \times Y}\) is defined by \((M_f)_{x,y} = 1\) if \(f\, x\, y = \mathrm{true}\) and \((M_f)_{x,y} = 0\) otherwise.
The rank of a Boolean function \(f : X \to Y \to \mathrm{Bool}\) is the \(\mathbb {R}\)-rank of its \(0/1\) matrix \(M_f\), i.e. \(\mathrm{rank}(f) = \mathrm{rank}_{\mathbb {R}}(M_f) \in \mathbb {N}\).
For a subset \(R \subseteq X \times Y\), the matrix \(M_R \in \mathbb {R}^{X \times Y}\) is defined by \((M_R)_{x,y} = 1\) if \((x,y) \in R\) and \((M_R)_{x,y} = 0\) otherwise.
If \(R \subseteq X \times Y\) is a combinatorial rectangle, i.e. \(R = A \times B\) for some \(A \subseteq X\) and \(B \subseteq Y\), then \(\mathrm{rank}(M_R) \le 1\). This follows because \(M_R\) is an outer product of the indicator vectors of \(A\) and \(B\).
For any two matrices \(A, B \in \mathbb {R}^{X \times Y}\),
For any finite index set \(\iota \), a finite set \(s \subseteq \iota \), and a family of matrices \(A : \iota \to \mathbb {R}^{X \times Y}\),
If \(\mathcal{P}\) is a monochromatic rectangle partition of a Boolean function \(f : X \to Y \to \mathrm{Bool}\), then \(\mathrm{rank}(f) \le |\mathcal{P}|\). The proof decomposes \(M_f\) as a sum of the indicator matrices of the \(1\)-coloured rectangles in \(\mathcal{P}\) and applies subadditivity of rank together with the fact that each such rectangle matrix has rank at most \(1\).
If the deterministic communication complexity of \(f : X \to Y \to \mathrm{Bool}\) is at most \(n \in \mathbb {N}\), then \(\mathrm{rank}(f) \le 2^n\).
For any Boolean function \(f : X \to Y \to \mathrm{Bool}\) (with \(X\) finite and \(Y\) a Fintype),
where \(\mathrm{DC}(f)\) is the deterministic communication complexity of \(f\), taken as an element of \(\mathbb {N}_\infty \).