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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2022

All Science Journal Classification (ASJC) codes

  • !!General Mathematics


أدرس بدقة موضوعات البحث “Anti-concentration and the exact gap-Hamming problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا