The Communication Complexity of Approximating Matrix Rank
Alexander A. Sherstov, Andrey A. Storozhenko · 2024
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\leqslant r 0$. Our result is an exponential improvement in$k$over previous work.