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 01 n , 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 ( frac 1 n ) . Extending Hal'asz work, we prove stronger bounds when the choices for x are unstructured. We also describe applications to communication complexity, randomness extraction and additive combinatorics.
展开▼
