Skip to content
Preprint

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

Oct 2026 · 1 citation · 24 references
Computer Science Physics

Abstract

We prove that the randomized communication complexity of Vector-in-Subspace in $\mathbb R^n$ with error at most $1/3$ is $\Theta(\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 $\Omega(n^{1/3})$ lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's $\Omega(\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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.