collaborators

1 paper

cs.CC2024

The Communication Complexity of Approximating Matrix Rank

Alexander A. Sherstov, Andrey A. Storozhenko

We fully determine the communication complexity of approximating matrix rank, over any finite field . We study the most general version of this problem, where $0\leq r<…