Communication Complexity of Integer Matrix Singularity
Abstract
Alice and Bob hold complementary halves of the columns of an n× n matrix of k-bit integers and decide whether it is singular over ℚ. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold n× n matrices A,B of k-bit integers and test the singularity of A+B over ℚ. We prove a bounded-error quantum lower bound Ω(min{n3/2√(klog n),n2log(nk)}) and a randomized upper bound O(n2min{k,log(k+log n)}). The bounds match at Θ(n2log(nk)) for k≥ nlog 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× n matrices A,B of k-bit integers and test whether their entrywise bitwise XOR A⊕ B is singular over ℚ, we prove a quantum lower bound Ω(n2k), 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.
Related
- On the quantum communication complexity of total functions
- Constant-round quantum advantage in communication complexity for total functions
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace
- Quantum Encodings, Private Messages, and Communication Complexity
BibTeX
@misc{wang2026communication,
title = {{Communication Complexity of Integer Matrix Singularity}},
author = {Chengu Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33521},
eprint = {2610.33521},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33521},
}
RIS
TY - UNPB
TI - Communication Complexity of Integer Matrix Singularity
AU - Chengu Wang
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33521
UR - https://arxiv.org/abs/2610.33521
AB - Alice and Bob hold complementary halves of the columns of an n× n matrix of k-bit integers and decide whether it is singular over ℚ. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold n× n matrices A,B of k-bit integers and test the singularity of A+B over ℚ. We prove a bounded-error quantum lower bound Ω(min{n^3/2√(klog n),n^2log(nk)}) and a randomized upper bound O(n^2min{k,log(k+log n)}). The bounds match at Θ(n^2log(nk)) for k≥ nlog 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× n matrices A,B of k-bit integers and test whether their entrywise bitwise XOR A⊕ B is singular over ℚ, 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.
ER -