{"id":"arxiv/2610.30052","url":"https://arxiv.org/abs/2610.30052","tags":["cs.CC","quant-ph"],"score":0,"title":"Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace","domain":"cs.CC","source":"arxiv","authors":["Chengu Wang"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-21","reactions":{}}