论文标题
抗浓度和确切的缝隙问题
Anti-concentration and the Exact Gap-Hamming Problem
论文作者
论文摘要
我们证明了两个独立随机向量的内部产物的抗浓缩界限，并使用这些边界证明了通信复杂性的下限。我们表明，如果$ a，b $是Cube $ \ {\ pm 1 \}^n $的子集，则使用$ | a | \ CDOT | B | \ geq 2^{1.01 n} $，$ x \ in a $和b $中的$ y \在b $中进行独立和均匀采样，然后内部产品$ \ langle x，y \ rangle $具有任何固定值，最多$ o（1/\ sqrt {n}）$。实际上，我们证明了以下更强的“平滑度”语句：$$ \ max_ {k} \ big | \ pr [\ langle x，y \ rangle = k] - \ pr [\ langle x，y \ rangle = k+4] \ big | | \ leq o（1/n）。$$我们使用这些结果来证明确切的差距障碍问题需要线性通信，从而解决了通信复杂性中的开放问题。我们还得出结论的抗浓度，以低熵的结构化分布。如果$ x \ in \ Mathcal {z}^n $没有零坐标，并且$ b \ subseteq \ {\ pm 1 \}^n $对应于$ \ nathcal {f} _2^n $ dimension dimension $ 0.51n $，然后$ 0.51N $，然后o（\ sqrt {\ ln（n）/n}）$。
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 $\{\pm 1\}^n$ with $|A| \cdot |B| \geq 2^{1.01 n}$, 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/\sqrt{n})$. In fact, we prove the following stronger "smoothness" statement: $$ \max_{k } \big| \Pr[\langle X,Y \rangle = k] - \Pr[\langle X,Y \rangle = k+4]\big| \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 anti-concentration for structured distributions with low entropy. If $x \in \mathcal{Z}^n$ has no zero coordinates, and $B \subseteq \{\pm 1\}^n$ corresponds to a subspace of $\mathcal{F}_2^n$ of dimension $0.51n$, then $\max_k \Pr[\langle x,Y \rangle = k] \leq O(\sqrt{\ln (n)/n})$.
