Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-140 | 17th September 2010 21:38

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance



We prove an optimal $\Omega(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.

ISSN 1433-8092 | Imprint