Anti-concentration and the Gap-Hamming problem

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 <X,Y> 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[<X,Y>=k] - Pr[<X,Y> = 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.