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.