Communication limits for testing matrix singularity with integers
Communication Complexity of Integer Matrix Singularity
Computational Complexity
Summary
The paper studies how hard it is for two people, each holding part of a big grid of numbers, to tell if the whole grid is special in a certain way (called singular). The researchers found how many bits of information they need to exchange to decide this, both when using random or quantum methods. They also looked at a similar problem when the two grids are combined differently, finding that this changes how the difficulty depends on the size of the numbers in the grid. The results set boundaries on the communication required even in specific, nearly full-rank cases.
What this means in practice
- •For distributed system designers: Know fundamental limits on how much data must be exchanged to verify matrix singularity when matrix data is split across nodes.
- •For quantum algorithm developers: Understand quantum communication lower bounds for matrix singularity testing to inform feasibility of distributed quantum protocols.
A theory result. No direct application yet.
Authors
Chengu Wang
Abstract
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 lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.