Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chicago Journal of Theoretical Computer Science

A concentration inequality for the overlap of a vector on a large set With application to the communication complexity of the Gap-Hamming-Distance problem

Thomas Vidick

Published Jan 1, 2012• 35 citations
Publisher

Abstract

Given two sets A, B ⊆ R n , a measure of their correlation is given by the expected squared inner product between random x ∈ A and y ∈ B. We prove an inequality showing that no two sets of large enough Gaussian measure (at least e -δ n for some constant δ > 0) can have correlation substantially lower than would two random sets of the same size.Our proof is based on a concentration inequality for the overlap of a random Gaussian vector on a large set.As an application, we show how our result can be combined with the partition bound of Jain and Klauck to give a simpler proof of a recent linear lower bound on the randomized communication complexity of the Gap-Hamming-Distance problem due to Chakrabarti and Regev.

DOI
10.4086/cjtcs.2012.001

Related papers

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

Chengu Wang

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.

cs.CCCross-listedarXiv:2610.30052•Oct 22, 2026•0 citations

The Communication Complexity of Gap Hamming Distance.

Alexander A. Sherstov

In the gap Hamming distance problem, two parties must determine whether their respective strings x,y ∈ {0,1} n are at Hamming distance less than n/2 − √ n or greater than n/2 + √ n. In a recent tour de force, Chakrabarti and Regev (2010) proved the long-conjectured Ω(n) lower bound on the randomized communication complexity of this problem. In follow-up work, Vidick (2010) discovered a simpler proof. We contribute a new proof, which is simpler yet and a page-and-a-half long.

Electronic colloquium on computational complexity•Jan 1, 2011•9 citations

Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays +2 more

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I)and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.

arXiv:1204.1505•Annual Symposium on Foundations of Computer Science•Oct 1, 2012•58 citations

Some Bounds on Communication Complexity of Gap Hamming Distance

Alexander Kozachinskiy

In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem ($\mathsf{GHD}^n_{L, U}$): Alice and Bob are given binary string of length $n$ and they are guaranteed that Hamming distance between their inputs is either $\le L$ or $\ge U$ for some $L < U$. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of $\mathsf{GHD}^n_{L, U}$ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates $O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)$ bits and has one-sided error probability $e^{-s}$ provided $s \ge \frac{(L + \frac{10}{n})^3}{U^2}$. Our second result is about deterministic communication complexity of $\mathsf{GHD}^n_{0,\, t}$. Surprisingly, it can be computed with logarithmic precision: $$\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),$$ where $V_2(n, r)$ denotes the size of Hamming ball of radius $r$. As an application of this result for every $c < 2$ we prove a $Ω\left(\frac{n(2 - c)^2}{p}\right)$ lower bound on the space complexity of any $c$-approximate deterministic $p$-pass streaming algorithm for computing the number of distinct elements in a data stream of length $n$ with tokens drawn from the universe $U = \{1, 2, \ldots, n\}$. Previously that lower bound was known for $c < \frac{3}{2}$ and for $c < 2$ but with larger $|U|$.

arXiv:1511.08854•Nov 27, 2015•1 citation

Lower Bounds on Quantum Multiparty Communication Complexity

Troy Lee, Gideon Schechtman, Adi Shraibman

A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.

IEEE Conference on Computational Complexity (CCC)•Jul 1, 2009•22 citations

Communication complexity of estimating correlations

Uri Hadar, Jingbo Liu, Yury Polyanskiy +1 more

We characterize the communication complexity of the following distributed estimation problem. Alice and Bob observe infinitely many iid copies of ρ-correlated unit-variance (Gaussian or ±1 binary) random variables, with unknown ρ∈[−1,1]. By interactively exchanging k bits, Bob wants to produce an estimate ρ of ρ. We show that the best possible performance (optimized over interaction protocol Π and estimator ρ) satisfies infΠ ρsupρE [|ρ−ρ|2] = k−1 (1/2 ln2 + o(1)). Curiously, the number of samples in our achievability scheme is exponential in k; by contrast, a naive scheme exchanging k samples achieves the same Ω(1/k) rate but with a suboptimal prefactor. Our protocol achieving optimal performance is one-way (non-interactive). We also prove the Ω(1/k) bound even when ρ is restricted to any small open sub-interval of [−1,1] (i.e. a local minimax lower bound). Our proof techniques rely on symmetric strong data-processing inequalities and various tensorization techniques from information-theoretic interactive common-randomness extraction. Our results also imply an Ω(n) lower bound on the information complexity of the Gap-Hamming problem, for which we show a direct information-theoretic proof.

arXiv:1901.09100•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•0 citations
Given two sets A, B ⊆ R n , a measure of their correlation is given by the expected squared inner product between random x ∈ A and y ∈ B. We prove an inequality showing that no two sets of large enough Gaussian measure (at least e -δ n for some constant δ > 0) can have correlation substantially lower than would two random sets of the same size.Our proof is based on a concentration inequality for the overlap of a random Gaussian vector on a large set.As an application, we show how our result can be combined with the partition bound of Jain and Klauck to give a simpler proof of a recent linear lower bound on the randomized communication complexity of the Gap-Hamming-Distance problem due to Chakrabarti and Regev.
We prove that the randomized communication complexity of Vector-in-Subspace in Rn\mathbb R^nRn with error at most 1/31/31/3 is Θ(n)Θ(\sqrt n)Θ(n​). Alice holds a unit vector uuu and Bob holds an n/2n/2n/2-dimensional subspace HHH; they must distinguish u∈Hu\in Hu∈H from u∈H⊥u\in H^\perpu∈H⊥. An exact one-way quantum protocol uses O(log⁡n)O(\log n)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)O(\sqrt n)O(n​) upper bound, improves the Ω(n1/3)Ω(n^{1/3})Ω(n1/3) lower bound of Klartag and Regev, and removes the total-rank restriction in Grupel's Ω(n)Ω(\sqrt n)Ω(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.
We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the γ2 method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2-O(I)and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braver man. First, we show that the information complexity of the Vector in Subspace Problem is O(n1/3), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an O(n) lower bound on the information complexity of the Gap Hamming Distance Problem.
In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (GHDL,Un\mathsf{GHD}^n_{L, U}GHDL,Un​): Alice and Bob are given binary string of length nnn and they are guaranteed that Hamming distance between their inputs is either ≤L\le L≤L or ≥U\ge U≥U for some L<UL < UL<U. They have to output 0, if the first inequality holds, and 1, if the second inequality holds. In this paper we study the communication complexity of GHDL,Un\mathsf{GHD}^n_{L, U}GHDL,Un​ for probabilistic protocols with one-sided error and for deterministic protocols. Our first result is a protocol which communicates O((sU)13⋅nlog⁡n)O\left(\left(\frac{s}{U}\right)^\frac{1}{3} \cdot n\log n\right)O((Us​)31​⋅nlogn) bits and has one-sided error probability e−se^{-s}e−s provided s≥(L+10n)3U2s \ge \frac{(L + \frac{10}{n})^3}{U^2}s≥U2(L+n10​)3​. Our second result is about deterministic communication complexity of GHD0, tn\mathsf{GHD}^n_{0,\, t}GHD0,tn​. Surprisingly, it can be computed with logarithmic precision: D(GHD0, tn)=n−log⁡2V2(n,⌊t2⌋)+O(log⁡n),\mathrm{D}(\mathsf{GHD}^n_{0,\, t}) = n - \log_2 V_2\left(n, \left\lfloor\frac{t}{2}\right\rfloor\right) + O(\log n),D(GHD0,tn​)=n−log2​V2​(n,⌊2t​⌋)+O(logn), where V2(n,r)V_2(n, r)V2​(n,r) denotes the size of Hamming ball of radius rrr. As an application of this result for every c<2c < 2c<2 we prove a Ω(n(2−c)2p)Ω\left(\frac{n(2 - c)^2}{p}\right)Ω(pn(2−c)2​) lower bound on the space complexity of any ccc-approximate deterministic ppp-pass streaming algorithm for computing the number of distinct elements in a data stream of length nnn with tokens drawn from the universe U={1,2,…,n}U = \{1, 2, \ldots, n\}U={1,2,…,n}. Previously that lower bound was known for c<32c < \frac{3}{2}c<23​ and for c<2c < 2c<2 but with larger ∣U∣|U|∣U∣.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.
We characterize the communication complexity of the following distributed estimation problem. Alice and Bob observe infinitely many iid copies of ρ-correlated unit-variance (Gaussian or ±1 binary) random variables, with unknown ρ∈[−1,1]. By interactively exchanging k bits, Bob wants to produce an estimate ρ of ρ. We show that the best possible performance (optimized over interaction protocol Π and estimator ρ) satisfies infΠ ρsupρE [|ρ−ρ|2] = k−1 (1/2 ln2 + o(1)). Curiously, the number of samples in our achievability scheme is exponential in k; by contrast, a naive scheme exchanging k samples achieves the same Ω(1/k) rate but with a suboptimal prefactor. Our protocol achieving optimal performance is one-way (non-interactive). We also prove the Ω(1/k) bound even when ρ is restricted to any small open sub-interval of [−1,1] (i.e. a local minimax lower bound). Our proof techniques rely on symmetric strong data-processing inequalities and various tensorization techniques from information-theoretic interactive common-randomness extraction. Our results also imply an Ω(n) lower bound on the information complexity of the Gap-Hamming problem, for which we show a direct information-theoretic proof.