Name
Abstract | ||
|---|---|---|
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 {+/- 1}(n) with vertical bar A vertical bar .vertical bar B vertical bar 2(1.01n), and X is an element of A and Y is an element of B are sampled independently and uniformly, then the inner product < X, Y > takes on any fixed value with probability at most O(1/root n). In fact, we prove the following stronger "smoothness" "statement: max(k) vertical bar Pr[< X, Y > = k] Pr[< X, Y >= k + 4] <= 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 is an element of Z(n) has no zero coordinates, and B subset of{+/- 1}(n) corresponds to a subspace of F-2(n) of dimension 0.51n, then max(k) Pr[< x, Y > = k <= O(root ln(n)/n). |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1137/21M1435288 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
communication complexity, anticoncentration, probability | Journal | 36 |
Issue | ISSN | Citations |
2 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anup Rao | 1 | 581 | 32.80 |
| Amir Yehudayoff | 2 | 0 | 0.34 |