Anti-concentration and the Exact Gap-Hamming Problem

DOI10.1137/21M1435288MaRDI QIDQ6387512arXivFDO

Authors Anup Rao, Amir Yehudayoff

Publication date 4 January 2022

Published in arXiv

Full work available at URL https://doi.org/10.1137/21M1435288

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11)

arXiv classification

math.PR

Abstract: 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 ${pm1}^n$ with $|A|cdot|B|geq{2}^{1.01n}$, and $XinA$ and $YinB$ are sampled independently and uniformly, then the inner product $langleX,Yangle$ takes on any fixed value with probability at most $O(1/sqrtn)$. In fact, we prove the following stronger "smoothness" statement: ${\displaystyle }$ max_{k } �ig| Pr[langle X,Y angle = k] - Pr[langle X,Y angle = k+4]�ig| leq O(1/n).${\displaystyle }$ 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 $xinmathcal{Z}^n$ has no zero coordinates, and $Bsubseteq{pm1}^n$ corresponds to a subspace of $mathcal{F}_2^n$ of dimension $0.51n$, then $ma{x}_{k}Pr[langlex,Yangle=k]leqO(sqrtln(n)/n)$.

This page was built for publication: Anti-concentration and the Exact Gap-Hamming Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6387512)