You are here

Anti-concentration in most directions

Anup Rao
Monday, February 24, 2020 - 2:30pm
Denny 110
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.
Event Type: 
Event Subcalendar: