随机 Set Disjointness 下界

要证明的结论 ​

Alice、Bob 各持 $A,B\subseteq [n]$，并约定 ${\mathrm{DISJ}}_n(A,B)=\mathbf{1}[A\cap B=\varnothing ]$。对任意固定常数 $0<\epsilon <1/2$，公共币、任意轮 bounded-error 通信复杂度满足 $R_{\epsilon }^{\mathrm{pub}}({\mathrm{DISJ}}_n)=\mathrm{\Omega }(n)$。

发送完整特征向量给出 $O(n)$ 上界，所以随机 Set Disjointness公理库Set Disjointness 通信问题Set Disjointness communication problem · DISJ communication problem判断双方私有集合是否没有共同元素的典型两方问题，其随机线性下界支撑大量空间与分布式下界。为 $\mathrm{\Theta }(n)$。本页完整展开从困难分布、固定随机币、抽取近单色大矩形到线性下界的归约链；核心 Razborov corruption 引理给出精确陈述与组合证明纲要，但不把其 switching 与谱估计的全部推导冒充为已展开证明。discrepancy 与信息复杂度公理库信息复杂度Information complexity · Information cost of a protocol以 transcript 对双方输入泄露的条件互信息度量协议的信息成本，并与实际通信 bit 数区分。也能提供下界框架，但不会与这条归约混成一串方法名。

为简化常数，先证明某个固定小错误 $\delta =1/100$ 的下界。任意其他常数 $\epsilon <1/2$ 可通过常数次独立重复和多数表决降到 $1/100$；若原协议通信为 $c$，放大后仍为 $O(c)$，所以小错误线性下界反推原协议也需 $\mathrm{\Omega }(n)$。

Razborov 困难分布 ​

取 $m=\lfloor n/4\rfloor$。令 ${\mu }_0$ 为所有满足 $|A|=|B|=m$ 且 $A\cap B=\varnothing$ 的集合对上的均匀分布；令 ${\mu }_1$ 为同样大小、但 $|A\cap B|=1$ 的集合对上的均匀分布。${\mu }_0$ 全部是输出 $1$ 的 yes 输入，${\mu }_1$ 全部是输出 $0$ 的 no 输入。

困难混合分布先以概率 $1/2$ 选择 $Z\in \{0,1\}$，再从 ${\mu }_Z$ 抽输入。它只支持合法的标准 DISJ 输入，因此在该 promise 子集上的下界也适用于没有集合大小限制的原问题。

核心 corruption 引理 ​

Razborov rectangle lemma 断言：存在绝对常数 $a,\gamma >0$，使每个组合矩形 $R=\mathcal{A}\times \mathcal{B}$ 都满足

$${\mu }_1(R)\ge a{\mu }_0(R)-2^{-\gamma n}.$$

换句话说，只要一个矩形在 disjoint 分布下的质量明显大于 $2^{-\gamma n}$，它在 unique-intersection 分布下就必须保留常数比例质量；不存在质量大的、几乎纯 disjoint 矩形。

引理针对 全部 集合族 $\mathcal{A},\mathcal{B}$，而不只针对由某个自然协议产生的规则矩形。这个全称量词让它能应用于任意轮协议的每个叶。

核心引理的组合证明纲要 ​

把 ${\mu }_0$ 输入看成两个不交 $m$-子集，把 ${\mu }_1$ 输入看成两个恰共享一个元素的 $m$-子集。构造局部 switching：从 disjoint 对 $(A,B)$ 中选择一个外部元素 $u$ 与 $A,B$ 中元素作交换，使新集合对产生唯一交点；反向 switch 删除该交点并恢复不交。

在完整输入空间里，正反 switching 的度数由 $n,m$ 决定并近乎正则。限制到矩形 $\mathcal{A}\times \mathcal{B}$ 后，若 unique-intersection 边远少于 disjoint 顶点，许多 switch 必须越出 $\mathcal{A}$ 或 $\mathcal{B}$。对这些边界作二次计数，并用 Johnson association scheme 的谱间隙控制集合族偏离均匀混合的程度，得到

$${\mu }_0(R)\le a^{-1}{\mu }_1(R)+2^{-\mathrm{\Omega }(n)}.$$

整理就是引理。加性指数项容纳极小或高度结构化矩形；线性通信证明只会从低成本协议抽取质量 $2^{-o(n)}$ 的叶，因此该异常项最终可被主项压过。

这一 switching/spectral 结论是证明的核心组合事实，不可由 fooling set 替代。Fooling set 要求每棵确定性树逐点正确，而引理允许矩形含一定 no 污染，正适合 bounded error。

从随机协议固定一棵树 ​

反设存在最坏通信 $c$、逐输入错误至多 $1/100$ 的公共币协议。它在混合分布下平均错误也至多 $1/100$。对公共随机串取平均，存在固定随机串 $r^{\ast }$，使所得确定性协议 $P$ 仍有分布错误 ${\mathrm{err}}_{({\mu }_0+{\mu }_1)/2}(P)\le 1/100$。

固定随机币不增加通信，所以 $P$ 的协议树深度仍至多 $c$，叶数至多 $2^c$。这一步是 Yao 的容易方向；困难分布已经在协议之前固定，不能针对每条随机树临时更换。

抽取一个大而近纯的 1-叶 ​

考察 $P$ 输出 $1$（disjoint）的叶矩形。它们在 ${\mu }_0$ 下正确覆盖的总质量至少 $1-2/100=0.98$；因为混合错误至多 $0.01$ 意味着 ${\mu }_0$ 条件错误至多 $0.02$。这些叶在 ${\mu }_1$ 下的总错误质量至多 $0.02$。

称满足 ${\mu }_1(R)>\frac{1}{10}{\mu }_0(R)$ 的叶 $R$ 为坏叶。

坏叶的 ${\mu }_0$ 总质量小于 $10\cdot 0.02=0.2$。所以好叶共同承载至少 $0.98-0.2=0.78$ 的 ${\mu }_0$ 质量。好叶不超过 $2^c$ 个，必有一个 $R^{\ast }$ 满足

$${\mu }_0(R^{\ast })\ge 0.78\cdot 2^{-c},{\mu }_1(R^{\ast })\le 0.1{\mu }_0(R^{\ast }).$$

这是从低错误协议到“大且近单色矩形”的完整抽取，常数都来自条件错误与叶数；不能只说 pigeonhole 而忘记先删除污染严重的叶。

应用 corruption 引理得到矛盾 ​

对 $R^{\ast }$ 应用 Razborov 引理：

$$0.1{\mu }_0(R^{\ast })\ge {\mu }_1(R^{\ast })\ge a{\mu }_0(R^{\ast })-2^{-\gamma n}.$$

取引理常数版本使 $a>0.1$，得到

$$(a-0.1){\mu }_0(R^{\ast })\le 2^{-\gamma n}.$$

再代入 ${\mu }_0(R^{\ast })\ge 0.78\cdot 2^{-c}$：

$$0.78(a-0.1)2^{-c}\le 2^{-\gamma n}.$$

取对数可得

$$c\ge \gamma n-O(1)=\mathrm{\Omega }(n),$$

与 $c=o(n)$ 的假设矛盾。证明不限制协议轮数；所有交互已被协议树的叶矩形统一吸收。

参数与方法边界 ​

若引理给出的常数 $a$ 小于预设污染阈值，就把阈值选为 $a/2$，并把协议错误通过常数次放大到足够小，使好叶仍保留正常数质量。数值 0.1 只是便于展示，逻辑依赖的是“污染阈值严格小于 corruption 常数”。

该证明使用集合大小 $m\approx n/4$ 和 unique-intersection 分布。把 hard distribution 换成独立 Bernoulli 集合后，矩形引理需要重新证明；不能只因边缘密度相近就保留 correlation 结构。

Public-coin 是比 private-coin 更强的模型，所以公共币下界自动推出私有币下界。量子协议的叶不形成同样的经典矩形划分，corruption 链不能原样推广。

信息复杂度路线会证明每个坐标贡献常数级条件信息并作 direct sum；它更适合摊还和组合定理。这里选择 corruption，是因为它把任意轮经典协议直接压到近单色矩形，并完成一条自洽的线性下界链。

参考资料

• Alexander A. Razborov, “On the Distributional Complexity of Disjointness,” Theoretical Computer Science 106(2), 1992, pp. 385–390.
• Bala Kalyanasundaram and Georg Schnitger, “The Probabilistic Communication Complexity of Set Intersection,” SIAM Journal on Discrete Mathematics 5(4), 1992, pp. 545–557.
• Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar, “An Information Statistics Approach to Data Stream and Communication Complexity,” FOCS, 2002, pp. 209–218.