{"id":"arxiv:2610.30052","kind":"preprint","title":"Tight Bounds on the Randomized Communication Complexity of Vector-in-Subspace","authors":["Chengu Wang"],"author_count":1,"year":2026,"published":"2026-10-21","venue":null,"cited_by":0,"doi":null,"arxiv_id":"2610.30052","nct_id":null,"source_url":"https://arxiv.org/abs/2610.30052","archive_url":"https://space-kitty.com/papers/arxiv:2610.30052","updated":"2026-10-21","pmid":null,"pmcid":null,"openalex_id":"W7223208187","pdf_url":"https://arxiv.org/pdf/2610.30052","abstract":"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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.CC","quant-ph"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"quantum-algorithms-advantage","name":"Quantum Algorithms & Quantum Advantage","domain_slug":"quantum-computing"}],"cited_in_dossiers":[]}