Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NUMBER-IN-HAND COMMUNICATION COMPLEXITY:
Reports tagged with number-in-hand communication complexity:
TR24-152 | 5th October 2024
Alexander A. Sherstov, Andrey Storozhenko

The Communication Complexity of Approximating Matrix Rank

We fully determine the communication complexity of approximating matrix rank, over any finite field $\mathbb{F}$. We study the most general version of this problem, where $0\leq r < R\leq n$ are given integers, Alice and Bob's inputs are matrices $A,B\in\mathbb{F}^{n\times n}$, respectively, and they need to distinguish between the cases ... more >>>




ISSN 1433-8092 | Imprint