Set Disjointness 的信息复杂度

困难分布刻意从不出现交点，因此只看输出熵会得到零：答案恒为“disjoint”。困难来自协议还必须对分布支撑外的 $(1,1)$ 坐标正确；transcript 若在三种零输入上完全相同，就无法在第四种输入上改变答案。

条件变量 $D_i$ 把相关的坐标分布拆成 product distributions，使 Alice 与 Bob 能各自补齐其他坐标。信息链式法则把总泄露平均到一位，Hellinger 几何再证明任何正确 AND 协议在该位必须泄露常数信息。

令 ${\mathrm{\Gamma }}_{uv}$ 是一 bit AND 输入 $(u,v)$ 下的 transcript 分布，${\mathrm{\Psi }}_{uv}(t)=\sqrt{\text{Pr}[{\mathrm{\Gamma }}_{uv}=t]}$。以 $h^2(P,Q)=\frac{1}{2}\Vert \sqrt{P}-\sqrt{Q}{\Vert }_2^2$ 为 Hellinger 平方距离；分别条件在两个等概率的 $D$ 取值上应用信息—距离不等式，再对 $D$ 平均，得到

由 Cauchy–Schwarz 与三角不等式，这至少是常数倍的 $\Vert {\mathrm{\Psi }}_{10}-{\mathrm{\Psi }}_{01}{\Vert }_2^2$。协议 transcript 的 rectangle factorization 给 cut-and-paste 恒等式

而 AND 在 $00$ 与 $11$ 上答案不同；错误至多 $\epsilon$ 迫使两分布的 Hellinger 距离至少为只依赖 $\epsilon$ 的正常数。于是单坐标成本为 ${\mathrm{\Omega }}_{\epsilon }(1)$，乘 $n$ 得线性界。这是可逐行复算的证明关键链，而非大矩形抽取。

本页路线与平滑矩形界公理库平滑矩形界Smooth rectangle bound · Smooth corruption bound以单一输出标签的分数矩形覆盖允许少量目标扰动，形成介于 smooth discrepancy 与 partition bound 之间的一侧下界。及Razborov corruption 证明公理库随机 Set Disjointness 下界：证明纲要Randomized Set Disjointness lower bound · Randomized DISJ lower bound在明确的困难分布上，用矩形腐败引理与错误放大推出随机 Disjointness 的线性下界，并标明引理的证明边界。不同：矩形路线排除大而近单色的输入块，这里则在零输入分布上用 transcript 距离、cut-and-paste 与 direct sum。把恒为 1 的分布输出熵当作信息成本会错误地得到零。

information cost 不超过通信，故立即得到 $R_{\epsilon }^{\mathrm{pub}}({\mathrm{DISJ}}_n)=\mathrm{\Omega }(n)$；发送一方的 $n$-bit 特征向量给出匹配的 $O(n)$ 上界。由信息等于摊销通信公理库摊销通信复杂度Amortized communication complexity · Information equals amortized communication在固定输入分布与逐坐标错误约定下，解释独立副本的极限平均通信，以及它与内部信息复杂度的精确关系。，同一线性信息下界还控制乘积分布下多副本的单位通信极限。

证明依赖坐标独立和 conditional mixture。若各坐标完全相关，链式法则不能产生 $n$ 份独立贡献；若协议只需在上述零输入支撑上正确，恒输出 1 的零通信协议就合法。量子、NOF 多方或有 promise 的其他 Disjointness 版本也需要各自的 cut-and-paste 与错误口径，不能从本定理自动继承。