{"id":"arxiv/2610.33521","url":"https://arxiv.org/abs/2610.33521","tags":["cs.CC","quant-ph"],"score":0,"title":"Communication Complexity of Integer Matrix Singularity","domain":"cs.CC","source":"arxiv","authors":["Chengu Wang"],"reviews":0,"subject":"cs.CC","summary":"Alice and Bob hold complementary halves of the columns of an $n\\times n$ matrix of $k$-bit integers and decide whether it is singular over $\\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\\min\\{n^{3/2}\\sqrt{k\\log n},n^2\\log(nk)\\})$ and a randomized upper bound $O(n^2\\min\\{k,\\log(k+\\log n)\\})$. The bounds match at $Θ(n^2\\log(nk))$ for $k\\ge n\\log n$. The…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-24","reactions":{}}