Source-linked AI summary
An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
Amit Chakrabarti, Oded Regev
TL;DR
The paper asks whether randomized two-way protocols for Gap-Hamming-Distance can use substantially less than linear communication. It proves an Ω(n) lower bound through a geometric analysis of Gaussian correlations and derives near-optimal multi-pass streaming space lower bounds.
Problem
The central question is whether randomized two-way communication for GHD requires Ω(n) bits, as conjectured beyond previously settled restricted models.
Method
The proof develops a geometric Gaussian-space statement and uses it to generalize the corruption method for communication lower bounds.
Results
Ω(n) bits are required by every randomized protocol solving GHD, including under uniformly random independent inputs.
Takeaways & Limitations
The result yields a multi-pass streaming space lower bound of Ω(ε^−2/p) and related lower bounds for frequency moments, empirical entropy, and functional monitoring.
Takeaways & Limitations
Existing discrepancy, corruption, and certain linear-algebraic methods do not establish the needed strong GHD lower bound, motivating the paper's generalized approach.
Abstract
from arXiv · showhide
We prove an optimal $Ω(n)$ lower bound on the randomized communication complexity of the much-studied Gap-Hamming-Distance problem. As a consequence, we obtain essentially optimal multi-pass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments. The Gap-Hamming-Distance problem is a communication problem, wherein Alice and Bob receive $n$-bit strings $x$ and $y$, respectively. They are promised that the Hamming distance between $x$ and $y$ is either at least $n/2+\sqrt{n}$ or at most $n/2-\sqrt{n}$, and their goal is to decide which of these is the case. Since the formal presentation of the problem by Indyk and Woodruff (FOCS, 2003), it had been conjectured that the naive protocol, which uses $n$ bits of communication, is asymptotically optimal. The conjecture was shown to be true in several special cases, e.g., when the communication is deterministic, or when the number of rounds of communication is limited. The proof of our aforementioned result, which settles this conjecture fully, is based on a new geometric statement regarding correlations in Gaussian space, related to a result of C. Borell (1985). To prove this geometric statement, we show that random projections of not-too-small sets in Gaussian space are close to a mixture of translated normal variables.
1 Introduction
The paper settles the conjecture that randomized two-way communication for Gap-Hamming-Distance requires linear communication, using a new geometric approach. This result yields near-optimal multi-pass streaming space lower bounds and related consequences.
- Main Result: The paper proves that every randomized protocol solving GHD must communicate Ω(n) bits.The same hardness holds under uniformly random independent inputs.
- Main Result: The result resolves the longstanding question of whether two-way randomized communication can beat the naive linear protocol.Earlier work established linear lower bounds only for restricted settings such as deterministic protocols, one-way communication, or bounded rounds.
- Technique: The proof generalizes the corruption method to handle large near-monochromatic rectangles that obstruct standard lower-bound techniques.Its core geometric ingredient is an anti-concentration statement for Hamming distances between points sampled from sufficiently large sets.
- Consequences: The communication theorem implies a multi-pass streaming space lower bound of Ω(ε^−2/p), tight up to logarithmic factors in m and n.Related reductions give lower bounds for frequency moments, empirical entropy, and functional monitoring.
2 Corruption, a Generalization, and the Main Theorem
The paper generalizes the corruption method with joker inputs and a Gaussian noise correlation inequality to prove linear randomized lower bounds for GHD, including under the uniform input distribution.
- Gaussian Ingredient: A new Gaussian noise correlation inequality supplies the technical ingredient needed to verify the joker-based conditions for GHD.The inequality is presented as the main technical contribution and is related to the smooth rectangle bound framework.
- Corruption With Jokers: The generalized conditions imply a distributional lower bound Dν,ε′(f) ≥ m + β and therefore a randomized lower bound Rε′(f) ≥ m + β.The hard distribution is ν := (α0µ0 + α1µ1)/(α0 + α1).
- Application to GHD: For GHD, the partial-function formulation assigns output 0 below t − g, output 1 above t + g, and leaves the intermediate region unspecified.The paper reduces the main argument to related threshold and gap settings before transferring the bound to standard GHD.
- Application to GHD: Applying the generalized corruption theorem and parameter-adjustment lemmas yields an asymptotically optimal randomized lower bound of Ω(n) for GHD.The intermediate result is Rε′(fb) ≥ δn + β for absolute constants, followed by adjustment of the threshold, gap, and error.
- Application to GHD: The same linear hardness holds when Alice and Bob receive uniformly random independent inputs, giving a clean hard distribution for GHD.This is stated as a separate hardness-under-uniform-distribution theorem.
3 An Inequality on Correlation under Gaussian Noise
The section develops a Gaussian-space correlation inequality through projection structure: most projections of sufficiently large sets resemble mixtures of translated normals, yielding anti-concentration under Gaussian noise. This statement transfers to the Boolean cube and supports the paper’s communication lower bound.
- 3.1 Projections of Sets in Gaussian Space: The technical goal is to characterize one-dimensional projections of a Gaussian distribution conditioned on a set of measure at least exp(−δn).The analysis asks how projections vary over unit directions when the conditioned set is not too small.
- 3.1 Projections of Sets in Gaussian Space: For sufficiently large sets, inner products between a conditioned Gaussian point and a random direction from another sufficiently large set cannot be too concentrated around zero.The resulting distribution is at least as spread out as a standard normal and may be more dispersed.
- 3.1 Projections of Sets in Gaussian Space: Theorem 3.1 shows that almost all projections are close to αX + Y, a mixture-like form with α between 1 − δ and 1.This generalizes earlier projection results by allowing arbitrary sufficiently large sets rather than imposing convexity or covariance assumptions.
- 3.1 Projections of Sets in Gaussian Space: The proof uses relative-entropy decompositions and nearly orthogonal directions: most sequential basis projections have small distance from Gaussianity, while large spherical sets contain n/2 nearly orthogonal vectors.These ingredients combine projection regularity with geometric coverage of the sphere.
- 3.2 The Correlation Inequality: The Gaussian inequality implies analogous Boolean-cube statements, including the stronger variant used to establish the Gap-Hamming-Distance lower bound.The paper identifies the Gaussian inequality and its proof as the main technical contributions.
4 Reductions, Related Results and Generalizations
This section uses simple reductions to extend the central Gap-Hamming-Distance lower bound across thresholds and gap sizes. It derives the general randomized complexity, proves hardness under uniform inputs, and notes related results for intersection size and inner product.
- Reductions: The reduction toolkit changes thresholds, gaps, and input lengths while preserving communication lower bounds.Its operations include gap amplification by repeating bits, padding inputs, and complementing Alice’s bits.
- Reductions: The reductions extend the Ω(n) lower bound to thresholds bounded away from the endpoints and gaps at most a constant multiple of √n.The resulting statement covers broad parameter settings beyond the centered problem.
- General Gap Sizes: For integers 1 ≤ g ≤ n, the randomized complexity is R(GHDn,n/2,g) = Θ(min{n, n^2/g^2}).The upper bound samples O(n^2/g^2) coordinates, while the lower bound follows by reduction to the central hard instance.
- Hardness Under Uniform Distribution: The Ω(n) lower bound also holds when Alice and Bob receive uniformly random independent inputs in {0,1}^n.The uniform distribution is the distribution ξ0 used in the hardness argument.
- Hardness Under Uniform Distribution: The uniform-distribution proof transforms padded inputs using shared random bitwise addition and coordinate permutation, then simulates a protocol for the centered problem.The transformed pair is uniformly distributed among inputs at the required Hamming distance, while preserving communication cost.
- Related Problems: Analogous results extend to GAP-INTERSECTION-SIZE and GAP-INNER-PRODUCT through reductions and hypercube embeddings.For GAP-INNER-PRODUCT, the simple O(1/ε^2) random-hyperplane protocol is tight when d ≥ 1/ε^2.