Anti-concentration and the exact gap-Hamming problem

Anup Rao, Amir Yehudayoff

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

We prove anticoncentration 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 21.01n, 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/\surd n). In fact, we prove the following stronger ``smoothness"" statement: maxk\bigm| \bigm| Pr[\langle X, Y \rangle = k] - Pr[\langle X, Y \rangle = k + 4]\bigm| \bigm| \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 anticoncentration for structured distributions with low entropy. If x \in \BbbZ n has no zero coordinates, and B \subseteq \{ \pm 1\} n corresponds to a subspace of \BbbF n2 of dimension 0.51n, then maxk Pr[\langle x, Y \rangle = k] \leq O(\sqrt{} ln(n)/n).

שפה מקוריתאנגלית
מספר המאמר2
עמודים (מ-עד)1071-1092
מספר עמודים22
כתב עתSIAM Journal on Discrete Mathematics
כרך36
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2022

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2600???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Anti-concentration and the exact gap-Hamming problem'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי