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.
AI Summary
The paper studies two-party communication for deciding whether a distributed $n\times n$ integer matrix is singular over $\mathbb Q$, with $k$-bit nonnegative entries. It compares additive sharing, testing $A+B$, with entrywise bitwise-XOR sharing, testing $A\oplus B$. Balanced column-partition singularity is equivalent to the additive formulation under local, corank-preserving reductions with constant-factor dimension growth.
For additive sharing, it proves the bounded-error entanglement-assisted quantum lower bound $\Omega(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a public-coin randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. These match at $\Theta(n^2\log(nk))$ for $k\ge n\log n$, including superpolynomial bit lengths. The upper bound has one-sided error: it always accepts singular matrices. It communicates modular kernel relations and quotient residues to remove prime factors from an implicit determinant. The lower bound combines a signed integer-matrix witness, Fourier/operator-norm estimates, and a local radix encoding that separates coefficient height from matrix dimension.
For XOR sharing, the paper proves $\Theta(n^2k)$ bounded-error complexity in both randomized and entanglement-assisted quantum models. The new quantum bit-length dependence follows from a dense weighted-equation witness, Fourier removal of exceptional dyadic frequencies, and a Schur-complement encoding into singularity. All lower bounds hold under the rank-$n-1$ versus rank-$n$ promise.
The principal unresolved regime is additive sharing with short entries: for Boolean inputs, the bounds remain $\Omega(n^{3/2}\sqrt{\log n})$ versus $O(n^2)$. Whether randomized and quantum complexities coincide throughout that regime is also open. Local computation is unrestricted; the protocols bound communication, not running time.
Little sign of AI-generated textAI use disclosed
The author used OpenAI Codex and Claude Code to assist with developing, checking, and simplifying proof arguments; researching related work and verifying citations; and drafting and revising the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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 Q. 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 Q. We prove a bounded-error quantum lower bound Ω(min{n3/2klogn,n2log(nk)}) and a randomized upper bound O(n2min{k,log(k+logn)}). The bounds match at Θ(n2log(nk)) for k≥nlogn. 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 Q, 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.
The paper studies two-party communication for deciding whether a distributed n×n integer matrix is singular over Q, with k-bit nonnegative entries. It compares additive sharing, testing A+B, with entrywise bitwise-XOR sharing, testing A⊕B. Balanced column-partition singularity is equivalent to the additive formulation under local, corank-preserving reductions with constant-factor dimension growth.
For additive sharing, it proves the bounded-error entanglement-assisted quantum lower bound Ω(min{n3/2klogn,n2log(nk)}) and a public-coin randomized upper bound O(n2min{k,log(k+logn)}). These match at Θ(n2log(nk)) for k≥nlogn, including superpolynomial bit lengths. The upper bound has one-sided error: it always accepts singular matrices. It communicates modular kernel relations and quotient residues to remove prime factors from an implicit determinant. The lower bound combines a signed integer-matrix witness, Fourier/operator-norm estimates, and a local radix encoding that separates coefficient height from matrix dimension.
For XOR sharing, the paper proves Θ(n2k) bounded-error complexity in both randomized and entanglement-assisted quantum models. The new quantum bit-length dependence follows from a dense weighted-equation witness, Fourier removal of exceptional dyadic frequencies, and a Schur-complement encoding into singularity. All lower bounds hold under the rank-n−1 versus rank-n promise.
The principal unresolved regime is additive sharing with short entries: for Boolean inputs, the bounds remain Ω(n3/2logn) versus O(n2). Whether randomized and quantum complexities coincide throughout that regime is also open. Local computation is unrestricted; the protocols bound communication, not running time.
We fully determine the communication complexity of approximating matrix rank, over any finite field F. We study the most general version of this problem, where0⩽r<R⩽nare given integers and Alice and Bob need to determine whether their respective matricesA,B∈Fn×nsatisfy rk(A+B)=rversus rk(A+B)=R. We show that this problem has commu-nication costΩ(r2log∣F∣), which is optimal. Our lower bound holds even for quantum protocols and even for error probability21(1−∣F∣−r/3), which too is optimal because this problem has a two-bit classical protocol with error21(1−∣F∣−Θ(r)). Prior to our work, lower bounds were known only for constant-error protocols and only for consecutive integersrandR, with no implication for the approximation of matrix rank. We also settle an analogous question for subspaces, where Alice has a subspaceS, Bob has a subspaceT) and they need to approximate the dimension of the subspaceS+Tgenerated bySandT(equivalently, approximate the dimension ofS∩T). As an application, we obtain anΩ(n2log∣F∣)/kmemory lower bound for any streaming algorithm withkpasses that approximates the rank of an input matrixM∈Fn×nwithin a factor of2−δ, for anyδ>0. Our result is an exponential improvement inkover previous work.
Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over the finite field F_p. Then, Clarkson and Woodruff [CW09] introduced the singularity problem to the streaming model. They proposed a randomized one pass streaming algorithm that uses O(k^2 log n) space to decide if the rank of a matrix is k, and proved an Omega(k^2) lower bound for randomized one-way protocols in the communication complexity model. We prove that the randomized/quantum communication complexity of the singularity problem over F_p is Omega(n^2 log p), which implies the same space lower bound for randomized streaming algorithms, even for a constant number of passes. The proof uses the framework by Lee and Shraibman [LS09], but we choose Fourier coefficients as the witness for the dual approximate norm of the communication matrix. Moreover, we use Fourier analysis to show the same randomized/quantum lower bound when deciding if the determinant of a non-singular matrix is a or b for non-zero a and b.
We prove that the randomized communication complexity of Vector-in-Subspace in Rn with error at most 1/3 is Θ(n). Alice holds a unit vector u and Bob holds an n/2-dimensional subspace H; they must distinguish u∈H from u∈H⊥. An exact one-way quantum protocol uses O(logn) qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's O(n) upper bound, improves the Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n) result.
The proof establishes a Gaussian moment bound over complete rectangle partitions. A complex Gaussian representation yields a vanishing even moment whose cancellation is preserved when averaging over the partition. We control the signed conditional moments around a real center by decomposing conditional Gaussian measures into fixed coordinates and sub-Gaussian components. Combining this estimate with spherical harmonic analysis gives the communication lower bound.
The level-k ℓ1-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations.In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol C computes an XOR function, then C(x,y) is a function of the parity x⊕y. This motivates us to analyze the XOR-fiber of the communication protocol C, defined as h(z):=Ex,y[C(x,y)∣x⊕y=z].We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight O(d) bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an d3/2⋅polylog(n) bound, which improves the previous O(d2) bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem.Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.
We study the communication complexity of a number of graph properties where the edges of the graph G are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.
We study the one-way communication complexity of the f-Boolean Hidden Partition problem. Here, Alice is given an n-bit string and Bob is given Ω(n) disjoint blocks of its indices together with a string of labels. Under the promise that the evaluations of f on these blocks either agree with all of the labels or disagree with all of them, Bob must determine which is the case using a single message from Alice. This problem generalizes the Boolean Hidden Matching and Hidden Hypermatching problems, which capture the special case where f is the parity function.
We establish classical and quantum communication bounds for f-Boolean Hidden Partition in terms of the sign degree d of f, proving a conjecture of Doriguello and Montanaro (TQC 2020). Their prior work gave logarithmic communication upper bounds for classical protocols when d≤1 and quantum protocols when d≤2, as well as polynomial lower bounds for certain structured functions with larger sign degree. We show that for every f of sign degree d≥2, the randomized classical communication complexity of this problem is Θ(n1−1/d) while its quantum communication complexity lies between Ω(n1−2/d) and $\bO{n^{1-1/\lceil d/2 \rceil} \log n}$. This completely characterizes the functions f admitting polynomial quantum advantage as those for which d≥2, with a new infinite family of exponential separations given by the case d=2.