betaFeedback

WorksComputer Science

Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace

Abstract

We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^n with error at most 1/31/3 is Θ(n)Θ(\sqrt n). Alice holds a unit vector uu and Bob holds an n/2n/2-dimensional subspace HH; they must distinguish u∈Hu\in H from u∈H⊥u\in H^\perp. An exact one-way quantum protocol uses O(log⁡n)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(n)O(\sqrt n) upper bound, improves the Ω(n1/3)Ω(n^{1/3}) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\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.

Paper details

vlnc:W_r8awvnm4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…