产品分布下集合不相交的上限

Question

对于通信复杂性的 2 方模型中的集合不相交问题，给 Alice 一个输入 $X$ 鲍勃得到输入 $Y$, $X$ 和 $Y$ 是 $n$-length 位串（从某个分布中采样），被解释为 $[n]$, ， IE。， $X_i=1$ 意味着 $i$第 位 $X$ 是在子集中。Alice 和 Bob 的目标是回答以下子集是否表示 $X$ 和 $Y$ 通过尽可能少的沟通而变得脱节。众所周知 $\欧米茄(n)$ 对于随机协议来说，在最坏的情况下位是必需的。

我看到了这本教科书的草稿 通信复杂性 作者：Anup Rao 和 Amir Yehudayoff, ，其中练习 6.8 提到 2 方集合不相交可以通过 预期的 数量 $O(n^{2/3}\log^2n)$ 如果 Alice 和 Bob 的输入是独立采样的。

考虑以下协议。如果有一个坐标 $j \in [n]$ 这样 $H(X_j)$ 和 $H(Y_j)$ 至少两者都是 $\epsilon$, ，然后 Alice 和 Bob 进行通信 $X_j,Y_j$. 。他们以看到的值为条件并重复此步骤，直到找不到这样的坐标。此时，Alice和Bob利用香农编码定理进行编码 $X$, $Y$. 。显示如何设置 $\epsilon$ 这样预期的通信就可以被限制为 $n^{2/3} \log^2 n$. 。暗示：利用以下事实： $H(X_j)\ge\epsilon$ 暗示 $Pr[X_j = 1] \ge \Omega(\epsilon/(\log(1/ε)))$.

我想这个想法是首先传达所有索引 $X$ 和 $Y$ 具有较大的熵，然后利用其余索引必须具有较小的熵这一事实。然而，协议的细节以及独立性在哪里 $X$ 和 $Y$ 进来了，我不清楚。

Answer 1

在算法的第一阶段，玩家放大高熵坐标。他们交换 $O(1)$ 位，并以概率在每一步停止 $\欧米茄(\epsilon^2/\log^2(1/\epsilon))$ （这里我们使用独立性）。因此这个阶段最多用完 $O(\log^2(1/\epsilon)/\epsilon^2)$ 期待中的位。第二阶段使用 $O(n\epsilon)$ 位。总的来说，我们预期使用了这么多位：$$ o（ log^2（1/ epsilon）/ epsilon^2 + epsilon n）。$$选择 $\epsilon = 1/n^{1/3}$ 以获得规定的界限。

如果没有独立性，我们就无法控制第一阶段每一步的停止概率。例如，可能是这样的 $X$ 随机均匀采样，并且 $Y$ 是的否定 $X$. 。在这种情况下，第一阶段永远不会停止，因此协议将始终使用 $2n$ 位。

顺便说一句，上限可以改进为 $O(\sqrt{n} \log n)$, ，几乎匹配下界 $\欧米茄(\sqrt{n})$ （文献中的差距可能已被缩小）。看 Pralahad Harsha 的讲义.