  We prove anti-concentration bounds for the inner product of two independent
random vectors, and use these bounds to prove lower bounds in communication
complexity. We show that if $A,B$ are subsets of the cube $\{\pm 1\}^n$ with
$|A| \cdot |B| \geq 2^{1.01 n}$, and $X \in A$ and $Y \in B$ are sampled
independently and uniformly, then the inner product $\langle X,Y \rangle$ takes
on any fixed value with probability at most $O(1/\sqrt{n})$. In fact, we prove
the following stronger "smoothness" statement: $$ \max_{k } \big| \Pr[\langle
X,Y \rangle = k] - \Pr[\langle X,Y \rangle = k+4]\big| \leq O(1/n).$$ We use
these results to prove that the exact gap-hamming problem requires linear
communication, resolving an open problem in communication complexity. We also
conclude anti-concentration for structured distributions with low entropy. If
$x \in \mathcal{Z}^n$ has no zero coordinates, and $B \subseteq \{\pm 1\}^n$
corresponds to a subspace of $\mathcal{F}_2^n$ of dimension $0.51n$, then
$\max_k \Pr[\langle x,Y \rangle = k] \leq O(\sqrt{\ln (n)/n})$.
