An optimal lower bound on the communication complexity of gap-hamming-distance

By Amit Chakrabarti, Oded Regev. 2010

189 citations recorded by the source corpus.

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+√n or at most n/2-√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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Communication lower bounds for statistical estimation problems via a distributed data processing inequality (2015, background): “Perhaps worth noting that similar intuition can be drawn for the two-party gap hamming distance problem but there we don’t have a completely information theoretic proof of the linear lower bound [CR11].”
Tight bounds for distributed functional monitoring (2011, background): “Arguably our proof is simpler than the recent GHD lower bounds.”
Optimal principal component analysis in distributed and streaming models (2015, unknown): “1 in [20]).”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, background): “The two-way communication complexity lower bound of Ω(n) was first established in [13], with later papers providing simplified proofs (see [32] for additional background.”
Two Party Distribution Testing: Communication and Security (2018, methodology): “To prove the theorem, we rely on the following communication complexity lower bound, which is a variant of the GapHamming lower bound [CR12, She12].”
Distributed low rank approximation of implicit functions of a matrix (2016, background): “[25] Each of Alice and Bob has an n-bit vector.”