TR10-140 Authors: Amit Chakrabarti, Oded Regev

Publication: 17th September 2010 21:40

Downloads: 2250

Keywords:

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.