We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $Θ(\sqrt n)$. Alice holds a unit vector $u$ and Bob holds an $n/2$-dimensional subspace $H$; they must distinguish $u\in H$ from $u\in H^\perp$. An exact one-way quantum protocol uses $O(\log n)$ qubits, making the problem a geometric example of an exponential quantum advantage over interactive classical communication. Our lower bound matches Raz's $O(\sqrt n)$ upper bound, improves the $Ω(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $Ω(\sqrt 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.
AI Summary
Vector-in-Subspace asks Alice, given a unit vector $u\in\mathbb R^n$, and Bob, given an $n/2$-dimensional subspace $H$, to distinguish $u\in H$ from $u\in H^\perp$. The paper determines its public-coin randomized communication complexity, allowing arbitrary interaction: $R_{1/3}(\mathrm{VSP}_n)=\Theta(\sqrt n)$. The lower bound improves the previous unrestricted $\Omega(n^{1/3})$ bound, matches Raz’s classical upper bound, and removes the total-rank restriction from an earlier $\Omega(\sqrt n)$ result. An exact one-way quantum protocol uses $\lceil\log_2 n\rceil$ qubits.
The main analytic result bounds Gaussian Wick-polynomial moments averaged over any complete partition into at most $2^d$ rectangles: $\mathbb E|\mathbb E[F_k\mid\mathsf T]|\le C^k k!(d+k^2)^k$. A complex Gaussian representation supplies a globally vanishing even moment. Conditioning on rectangles and decomposing Alice’s conditional Gaussian law into fixed coordinates and sub-Gaussian residual components permits control of signed moments around a real center. Crucially, cancellation is retained across the complete partition before taking absolute values. Polynomial-moment estimates provide both partition-norm and Frobenius-norm control of the residual Wick tensors.
Spherical harmonic analysis, a Gaussian lift, and smoothing transfer this estimate to protocol advantage. The new estimate controls low harmonic levels, while hypercontractivity and the exact subspace-transform spectrum handle higher levels, establishing the lower bound for $d$ below a constant multiple of $\sqrt n$.
The stated theorem concerns the exact membership promise and communication cost, not computational efficiency. The matching classical protocol may require substantial local computation.
No 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.
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.
Vector-in-Subspace asks Alice, given a unit vector u∈Rn, and Bob, given an n/2-dimensional subspace H, to distinguish u∈H from u∈H⊥. The paper determines its public-coin randomized communication complexity, allowing arbitrary interaction: R1/3(VSPn)=Θ(n). The lower bound improves the previous unrestricted Ω(n1/3) bound, matches Raz’s classical upper bound, and removes the total-rank restriction from an earlier Ω(n) result. An exact one-way quantum protocol uses ⌈log2n⌉ qubits.
The main analytic result bounds Gaussian Wick-polynomial moments averaged over any complete partition into at most 2d rectangles: E∣E[Fk∣T]∣≤Ckk!(d+k2)k. A complex Gaussian representation supplies a globally vanishing even moment. Conditioning on rectangles and decomposing Alice’s conditional Gaussian law into fixed coordinates and sub-Gaussian residual components permits control of signed moments around a real center. Crucially, cancellation is retained across the complete partition before taking absolute values. Polynomial-moment estimates provide both partition-norm and Frobenius-norm control of the residual Wick tensors.
Spherical harmonic analysis, a Gaussian lift, and smoothing transfer this estimate to protocol advantage. The new estimate controls low harmonic levels, while hypercontractivity and the exact subspace-transform spectrum handle higher levels, establishing the lower bound for d below a constant multiple of n.
The stated theorem concerns the exact membership promise and communication cost, not computational efficiency. The matching classical protocol may require substantial local computation.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x∈{0,1}n, and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple ⟨i,j,b⟩ such that the edge (i,j) belongs to the matching M and b=xi⊕xj. We prove that the quantum one-way communication complexity of HMn is O(logn), yet any randomized one-way protocol with bounded error must use Ω(n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM), and hence we provide the first exponential separation between quantum SM and randomized SM with public coins. For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(logn) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(3nlogn) bits of communication.
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.
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions p and q over domains X and Y, respectively. Their goal is to estimate Ex∼p,y∼q[f(x,y)] to within additive error ε for a bounded function f, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of f and the error parameter ε. The random sampling approach -- estimating the mean by averaging f over O(1/ε2) random samples -- requires O(R(f)/ε2) total communication, where R(f) is the randomized communication complexity of f. We design a new debiasing protocol which improves the dependence on 1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HMn: Alice gets as input a string x ∈ (0, 1)n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching M and b = xi ⊕ xj. We prove that the quantum one-way communication complexity of HMn is O(log n), yet any randomized one-way protocol with bounded error must use Ω(√n) bits of communication. No asymptotic gap for one-way communication was previously known. Our bounds also hold in the model of Simultaneous Messages (SM) and hence we provide the first exponential separation between quantum SM and randomized SM with public coins.For a Boolean decision version of HMn, we show that the quantum one-way communication complexity remains O(log n) and that the 0-error randomized one-way communication complexity is Ω(n). We prove that any randomized linear one-way protocol with bounded error for this problem requires Ω(√[3] n log n) bits of communication.
We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(\log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].
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.