Anti-concentration in most directions

Abstract

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 $\{\pm 1{\}}^n$ with $|A|\cdot |B|\ge 2^{1.01n}$, and $X\in A$ and $Y\in B$ are sampled independently and uniformly, then the inner product $⟨X,Y⟩$ takes on any fixed value with probability at most $O(\frac{1}{\sqrt{n}})$. Extending Halász work, we prove stronger bounds when the choices for $x$ are unstructured. We also describe applications to communication complexity, randomness extraction and additive combinatorics.

23 pages