The Communication Complexity of Approximating Matrix Rank

We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$0\leqslant r &lt; R\leqslant n$</tex> are given integers and Alice and Bob need to determine whether their respective matrices <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$A, B\in \mathbb{F}^{n\times n}$</tex> satisfy rk <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(A+B)=r$</tex> versus rk <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(A+B)=R$</tex>. We show that this problem has commu-nication cost <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(r^{2}\log\vert \mathbb{F}\vert)$</tex>, which is optimal. Our lower bound holds even for quantum protocols and even for error probability <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-r/3})$</tex>, which too is optimal because this problem has a two-bit classical protocol with error <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{1}{2}(1-\vert \mathbb{F}\vert ^{-\Theta(r)})$</tex>. Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integers <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$r$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$R$</tex>, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspace <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex>, Bob has a subspace <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex>) and they need to approximate the dimension of the subspace <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S+T$</tex> generated by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$T$</tex> (equivalently, approximate the dimension of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S\cap T$</tex>). As an application, we obtain an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(n^{2}\log\vert \mathbb{F}\vert)/k$</tex> memory lower bound for any streaming algorithm with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> passes that approximates the rank of an input matrix <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M\in \mathbb{F}^{n\times n}$</tex> within a factor of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\sqrt{2}-\delta$</tex>, for any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\delta &gt; 0$</tex>. Our result is an exponential improvement in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> over previous work.