随机 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 数区分。也能提供下界框架，但不会与这条归约混成一串方法名。

先把协议错误放大到一个稍后按 corruption 常数选定的固定小量 $\delta >0$。任意常数 $\epsilon <1/2$ 都可通过常数次独立重复和多数表决降到该阈值；若原协议通信为 $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$、逐输入错误至多 $\delta$ 的公共币协议。它在混合分布下平均错误也至多 $\delta$。对公共随机串取平均，存在固定随机串 $r^{\ast }$，使所得确定性协议 $P$ 仍有分布错误 ${\mathrm{err}}_{({\mu }_0+{\mu }_1)/2}(P)\le \delta$。

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

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

考察 $P$ 输出 $1$（disjoint）的叶矩形。混合错误至多 $\delta$ 意味着两类条件错误各至多 $2\delta$，所以这些叶在 ${\mu }_0$ 下正确覆盖的总质量至少 $1-2\delta$，在 ${\mu }_1$ 下的总错误质量至多 $2\delta$。

令污染阈值 $\eta =a/2$，称满足 ${\mu }_1(R)>\eta {\mu }_0(R)$ 的叶 $R$ 为坏叶。

坏叶的 ${\mu }_0$ 总质量小于 $2\delta /\eta$。预先把 $\delta$ 选得足够小，使 $\rho =1-2\delta -2\delta /\eta >0$。于是好叶共同承载至少 $\rho$ 的 ${\mu }_0$ 质量。好叶不超过 $2^c$ 个，必有一个 $R^{\ast }$ 满足

$${\mu }_0(R^{\ast })\ge \rho 2^{-c},{\mu }_1(R^{\ast })\le \eta {\mu }_0(R^{\ast }).$$

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

应用 corruption 引理得到矛盾 ​

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

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

因为 $\eta =a/2$，得到

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

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

$$\frac{\rho a}{2}{2}^{-c}\le 2^{-\gamma n}.$$

取对数可得

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

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

直觉

困难分布把问题压到两层几乎相邻的集合对：要么完全不交，要么恰有一个交点。低通信协议只能把输入空间切成少量矩形；若它在 disjoint 输入上大多答对，就必须有一片叶同时承载可观质量且很少混入 unique-intersection 输入。

Razborov 引理恰好否定这种叶。矩形限制 Alice 与 Bob 的集合族独立组合，无法在保持较大 ${\mu }_0$ 质量的同时系统性排除所有单交点配对；switching 把不交对推向单交点对，谱估计则控制一个大集合族能有多严重的边界偏斜。协议的低错误因此与矩形的不可纯化直接冲突。

证明链中的每一环承担不同量词：固定随机币把协议分布化为一棵树，删除坏叶控制颜色污染，pigeonhole 从有限叶数抽出大块，corruption 引理再排除这块。省略任何一环，都无法从“平均上多数答案正确”跳到“存在大而近单色的矩形”。

例子与边界

参数与方法边界 ​

污染阈值必须严格小于 corruption 常数，协议错误则需放大到使 $\rho >0$ 的固定小量。正文取 $\eta =a/2$，正是为了让这两个常数关系直接进入不等式，而不是依赖未经核对的十进制阈值。

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

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

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

推论与应用

下界对公共币、任意轮协议成立，因此也自动覆盖较弱的私有币协议和受限轮数协议。与发送完整特征向量的 $O(n)$ 上界合并，得到经典 bounded-error Set Disjointness 的紧确量级 $\mathrm{\Theta }(n)$。

这条定理是许多 streaming 与分布式下界的困难源：若目标算法的内存状态或跨节点消息能模拟成低通信 DISJ 协议，线性通信障碍就会转移过去。归约仍需保留集合大小、错误概率、随机币可见性、轮数和输入分割；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.