We prove new lower bounds on the well known Gap-Hamming problem in communication complexity. Our main technical result is an anti-concentration bound for the inner product of two independent random vectors. We show that if A, B are arbitrary subsets of the cube {±1}^n with |A| · |B| ≥ 2^(1.01n), and X ∈ A and Y ∈ B are sampled independently and uniformly, then the inner product must be anti-concentrated: it takes on any fixed value with probability at most O(1/sqrt(n)). In fact, the following stronger claim holds: for any integer k, |Pr[=k] - Pr[ = k+4]| is at most O(1/n). Remarkably, this last claim is false if 4 is replaced with an integer that is not divisible by 4. I will explain why this happens in my talk.   This is joint work with Amir Yehudayoff.