Anti-concentration in most directions

We prove anti-concentration bounds for the inner product of two independent random vectors. For example, we show that if A, B are 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> takes on any fixed value with probability at most O( 1/√n ). Extending Halasz work, we prove stronger bounds when the choices for x are unstructured. We also describe applications to communication complexity and additive combinatorics.