Anti-concentration in most directions

2018/11/15 by Anup Rao, Rao, Anup, Amir Yehudayoff +1 · 1 citation
Computer Science · Mathematics · #60C05 #68Q87 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1811.06510

openalex publication_date 2018/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 \± 1\ⁿ 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(\tfrac1√(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.

Citations

• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited by

• A LYM Inequality For Product Measures

Related

• Anti-concentration and the Exact Gap-Hamming Problem
• A relative anti-concentration inequality
• Anti-concentration for polynomials of independent random variables
• The anti-concentration phenomenon with respect to random permutations
• Concentration inequalities for some negatively dependent binary random variables