  The Gap-Hamming-Distance problem arose in the context of proving space lower
bounds for a number of key problems in the data stream model. In this problem,
Alice and Bob have to decide whether the Hamming distance between their $n$-bit
input strings is large (i.e., at least $n/2 + \sqrt n$) or small (i.e., at most
$n/2 - \sqrt n$); they do not care if it is neither large nor small. This
$\Theta(\sqrt n)$ gap in the problem specification is crucial for capturing the
approximation allowed to a data stream algorithm.
  Thus far, for randomized communication, an $\Omega(n)$ lower bound on this
problem was known only in the one-way setting. We prove an $\Omega(n)$ lower
bound for randomized protocols that use any constant number of rounds.
  As a consequence we conclude, for instance, that $\epsilon$-approximately
counting the number of distinct elements in a data stream requires
$\Omega(1/\epsilon^2)$ space, even with multiple (a constant number of) passes
over the input stream. This extends earlier one-pass lower bounds, answering a
long-standing open question. We obtain similar results for approximating the
frequency moments and for approximating the empirical entropy of a data stream.
  In the process, we also obtain tight $n - \Theta(\sqrt{n}\log n)$ lower and
upper bounds on the one-way deterministic communication complexity of the
problem. Finally, we give a simple combinatorial proof of an $\Omega(n)$ lower
bound on the one-way randomized communication complexity.
