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 0 r < R n are given integers, Alice and Bob's inputs are matrices A, B ∈ F n×n , respectively, and they need to distinguish between the cases rk(A + B) = r and rk(A + B) = R. We show that this problem has randomized communication complexity Ω(1 + r 2 log |F|). This is optimal in a strong sense because O(1 + r 2 log |F|) communication is sufficient to determine, for arbitrary A, B, whether rk(A + B) r. Prior to our work, lower bounds were known only for consecutive integers r and R, with no implication for the approximation of matrix rank. Our lower bound holds even for quantum protocols and even for error probability 1 2 -1 4 |F| -r/3 , which too is virtually optimal because the problem has a two-bit classical protocol with error 1 2 -Θ(|F| -r ). As an application, we obtain an Ω( 1 k • n 2 log |F|) space lower bound for any streaming algorithm with k passes that approximates the rank of an input matrix M ∈ F n×n within a factor of √ 2δ, for any δ > 0. Our result is an exponential improvement in k over previous work.

We also settle the randomized and quantum communication complexity of several other linearalgebraic problems, for all settings of parameters. This includes the determinant problem (given matrices A and B, distinguish between the cases det(A + B) = a and det(A + B) = b, for fixed field elements a = b) and the subspace sum and subspace intersection problem (given subspaces S and T of known dimensions m and ℓ, respectively, approximate the dimensions of S + T and S ∩ T ).