Gap Hamming Distance is a well-studied problem in communication
complexity, in which Alice and Bob have to decide whether the Hamming
distance between their respective $n$-bit inputs is less than
$n/2-\sqrt{n}$ or greater than $n/2+\sqrt{n}$.  We show that every
$k$-round bounded-error communication protocol for this problem sends
a message of at least $\Omega(n/(k^2\log k))$ bits.  This lower bound
has an exponentially better dependence on the number of rounds than
the previous best bound, due to Brody and Chakrabarti.  Our
communication lower bound implies strong space lower bounds on algorithms
for a number of data stream and distributed computations, such as
approximating the number of distinct elements in a stream.
