2024/10/26 by Alexander A. Sherstov, Sherstov, Alexander A., Andrey A. Storozhenko +1 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Neural Networks and Applications #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2410.20094
openalex publication_date 2024/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We fully determine the communication complexity of approximating matrix rank, over any finite field \mathbbF. We study the most general version of this problem, where 0≤ r0. Our result is an exponential improvement in k over previous work. We also settle the randomized and quantum communication complexity of several other linear-algebraic 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).