Set Disjointness 的信息复杂度

形式陈述

固定整数 $n\ge1$ ，令集合不相交函数 $\operatorname{DISJ}_n(x,y)=1$ 当且仅当没有坐标满足 $x_i=y_i=1$ 。采用信息复杂度中的有限深度二进制协议：发言者和终止由公共币 $R$ 与公开前缀确定；双方私有随机带独立，可以重复使用； $T$ 只记录真正传送的消息。指定 Bob 输出，允许输出还依赖他的输入和私有带。公共币独立于输入，错误要求是每个输入上至多 $0\le\varepsilon<1/2$ ，通信是硬上限。对数以二为底， $\ln$ 表示自然对数。

分析分布逐坐标独立生成。先抽公平比特 $D_i$ ：若 $D_i=0$ ，令 $X_i=0$ 、 $Y_i$ 为公平比特；若 $D_i=1$ ，令 $Y_i=0$ 、 $X_i$ 为公平比特。记 $Z_i=(X_i,Y_i)$ ，其边缘分布为

\Pr[Z_i=00]=\frac12, \qquad \Pr[Z_i=01]=\Pr[Z_i=10]=\frac14.

$D^n$ 是证明中的条件变量，原协议看不到它。定义条件外部信息成本

\operatorname{CIC}(\Pi)=I(Z^n;T\mid D^n,R).

本文完整证明以下显式版本：

\boxed{ \operatorname{CIC}(\Pi)\ge c_\varepsilon n, \qquad c_\varepsilon=\frac{(1-2\varepsilon)^2}{40\ln2}>0. }

于是最坏通信至少为 $c_\varepsilon n$ 。方法来自 Bar-Yossef–Jayram–Kumar–Sivakumar 的条件信息直和与 Hellinger 几何；这里的保守常数和私有输出处理由下文逐步推出，不作为原论文的最优常数引用。[1]

直觉

困难分布从不出现交点，因而正确答案恒为一，输出熵为零。但协议还必须在分布支撑外的交点输入上正确。合法消息记录的因子分解把这些输入联系起来：三个无交点输入的消息分布如果全部太接近，第四个输入就不能被 Bob 可靠识别。

证明分两层。先证明一对比特的 AND 必须在无交点分布上泄露正常数信息；再用条件熵把一个长协议的成本拆成逐坐标下界。 $D_i$ 的作用是让双方能各自在本地生成填充输入，而不必知道对方的随机比特。

例子与边界

一 bit AND：输出恒零，消息仍有信息

令 $(U,V,D)$ 按上述单坐标分布生成。Alice 只发送 $T=U$ ，Bob 本地输出 $U\land V$ 。这个协议对全部四种输入都正确。条件在 $D=0$ 时消息恒为零，条件在 $D=1$ 时消息是公平比特，故

I(U,V;T\mid D)=\frac12\cdot0+\frac12\cdot1=\frac12.

边缘上 $\Pr[U=1]=1/4$ ，外部信息则为 $I(U,V;T)=h_2(1/4)\approx0.811278$ bit；无交点分布上的 AND 输出恒零。条件信息、外部信息和输出熵是三个不同的量。

记四个输入下的消息分布为 $\Gamma_{uv}$ 。此例有

\Gamma_{00}=\Gamma_{01}=\delta_0, \qquad \Gamma_{10}=\Gamma_{11}=\delta_1.

因此不能只凭 AND 在 $00$ 与 $11$ 上答案不同，就不加解释地断言“任何输出都是消息的函数”。Bob 的输出还使用本地 $V$ 。下面会比较具有相同 Bob 输入的 $01$ 与 $11$ ，并证明他的私有带也不会破坏这个比较。

两坐标：直和何时严格

Alice 发送 $X_1X_2$ ，Bob 判断是否与 $Y_1Y_2$ 相交。给定 $D^2$ ，每个 $D_i=1$ 贡献一个公平的 $X_i$ ，因此成本表是：

$D^2$	条件信息成本	原因
$00$	$0$	两个 $X_i$ 都为零
$01$	$1$	只有 $X_2$ 随机
$10$	$1$	只有 $X_1$ 随机
$11$	$2$	两个独立公平比特

四行等概率，总成本为一 bit，两项逐坐标信息各为 $1/2$ 。

再看一个合法消息 $T=X_1\oplus X_2$ 。它不是 DISJ 求解协议，只用来检查信息不等式。四行总信息分别为 $0,1,1,1$ ，平均 $3/4$ ；每个坐标单独与 $T$ 的条件互信息平均为 $1/4$ ，两项和只有 $1/2$ 。在 $D^2=11$ 时，奇偶位不泄露任一单独比特，却泄露二者的联合信息。因此直和步骤一般是“至少”，不是等式。

推论与应用

单坐标 AND 的完整距离证明

信息如何控制 Hellinger 距离

先考虑任意正确的 AND 协议，记其公共随机性为 $Q$ ，把公共币连同消息纳入分布 $\Gamma_{uv}=\mathcal L(Q,T\mid U=u,V=v)$ 。这保留对全部公共币的平均正确率，不要求固定每个公共种子后仍然正确。

对两个分布定义

h^2(P,Q)=1-\sum_z\sqrt{P(z)Q(z)} =\frac12\|\sqrt P-\sqrt Q\|_2^2.

这里 $h$ 是距离，满足三角不等式； $h^2$ 一般不满足。为简洁先写离散随机串的求和形式；一般随机带可相对于共同支配测度写同样的密度积分，下面的 Jensen 和 Cauchy–Schwarz 论证不变。

令 $M=(P+Q)/2$ ，用以 bit 为单位的KL 散度定义 Jensen–Shannon 散度为

\operatorname{JS}_2(P,Q) =\frac12D_{\mathrm{KL},2}(P\|M) +\frac12D_{\mathrm{KL},2}(Q\|M).

对 $P$ 应用Jensen 不等式，再用 $-\ln s\ge1-s$ ，得到

\begin{aligned} D_{\mathrm{KL},2}(P\|M) &=-\frac2{\ln2}E_P\ln\sqrt{\frac MP}\\ &\ge-\frac2{\ln2}\ln\sum_z\sqrt{P(z)M(z)}\\ &\ge\frac2{\ln2}h^2(P,M). \end{aligned}

零概率项按极限解释， $M\ge P/2$ 保证这里没有来自分母的困难。再用 $h(P,Q)\le h(P,M)+h(M,Q)$ 及 $(s+t)^2\le2(s^2+t^2)$ ，可得

\operatorname{JS}_2(P,Q) \ge\frac{h^2(P,M)+h^2(Q,M)}{\ln2} \ge\frac{h^2(P,Q)}{2\ln2}.

给定 $D=0$ ，只有 $00,01$ 两个等概率输入；给定 $D=1$ ，只有 $00,10$ 。 $Q$ 独立于 $(U,V,D)$ ，于是单坐标成本恰为

\begin{aligned} \mathcal I &=I(U,V;T\mid D,Q)=I(U,V;Q,T\mid D)\\ &=\tfrac12\operatorname{JS}_2(\Gamma_{00},\Gamma_{01}) +\tfrac12\operatorname{JS}_2(\Gamma_{00},\Gamma_{10})\\ &\ge\frac{a^2+b^2}{4\ln2}, \end{aligned}

其中 $a=h(\Gamma_{00},\Gamma_{01})$ 、 $b=h(\Gamma_{00},\Gamma_{10})$ 。

因子分解如何跨过分布支撑

固定 $(q,t)$ 。执行与完整消息记录 $t$ 一致，等价于 Alice 的私有带满足只依赖 $(u,q,t)$ 的约束，以及 Bob 的私有带满足只依赖 $(v,q,t)$ 的约束。独立私有带给出

\Gamma_{uv}(q,t)=\Pr[Q=q]\alpha_u(q,t)\beta_v(q,t).

即使每方多次使用同一条私有带，这仍成立：每次发言只是给相应一方的可用随机带集合增加约束。于是逐点有

\Gamma_{00}(q,t)\Gamma_{11}(q,t) =\Gamma_{01}(q,t)\Gamma_{10}(q,t).

开平方后求和，得到 cut-and-paste 恒等式

h(\Gamma_{00},\Gamma_{11}) =h(\Gamma_{01},\Gamma_{10}).

这一步只用了合法协议结构，没有要求四种输入在困难分布中都有正概率。

私有输出如何迫使距离为正

给定 $(u,v,q,t)$ 后，Bob 私有带的后验是其原分布限制到上述 Bob 约束集合。归一化时 Alice 因子消去，因此这个后验只依赖 $(v,q,t)$ 。所以固定 $v=1$ ，Bob 的最终输出是作用于 $(Q,T)$ 的同一个随机通道，不因 Alice 的输入 $u$ 改变。

在 $01$ 上，输出一的概率至多 $\varepsilon$ ；在 $11$ 上至少 $1-\varepsilon$ 。总变差经同一随机通道不能增加：对任意输出事件 $E$ ，通道概率 $K(E\mid q,t)$ 位于 $[0,1]$ ，把 $2K(E\mid q,t)-1$ 代入总变差的有界函数对偶式，便知该事件的概率差不超过输入分布的总变差。因此

\operatorname{TV}(\Gamma_{01},\Gamma_{11})\ge1-2\varepsilon.

直接对 $|p-q|=|\sqrt p-\sqrt q|(\sqrt p+\sqrt q)$ 使用Cauchy–Schwarz 不等式，得到

\operatorname{TV}(P,Q) \le h(P,Q)\sqrt{2-h^2(P,Q)}\le\sqrt2\,h(P,Q).

另一方面，cut-and-paste 与两次三角不等式给出

\begin{aligned} h(\Gamma_{01},\Gamma_{11}) &\le a+h(\Gamma_{00},\Gamma_{11})\\ &=a+h(\Gamma_{01},\Gamma_{10})\le2a+b,\\ h^2(\Gamma_{01},\Gamma_{11})&\le5(a^2+b^2). \end{aligned}

把三条界接起来，单坐标成本满足

\mathcal I \ge\frac{h^2(\Gamma_{01},\Gamma_{11})}{20\ln2} \ge\frac{(1-2\varepsilon)^2}{40\ln2}=c_\varepsilon.

整个证明没有向 transcript 偷加一个输出 bit，也没有把每个坐标各加的一位在求和后忽略。

条件熵直和与每个坐标的实际协议

给定 $(D^n,R)$ ， $Z_1,\ldots,Z_n$ 独立。先展开输入熵，再对后验条件熵用次可加性：

\begin{aligned} I(Z^n;T\mid D^n,R) &=\sum_{i=1}^nH(Z_i\mid D^n,R) -H(Z^n\mid T,D^n,R)\\ &\ge\sum_{i=1}^n \bigl[H(Z_i\mid D^n,R)-H(Z_i\mid T,D^n,R)\bigr]\\ &=\sum_{i=1}^n I(Z_i;T\mid D^n,R). \end{aligned}

这不是“给互信息增加条件只会减小”的错误规则。每一个右端项还需要对应到一个真正可执行的 AND 协议。

固定坐标 $i$ 。Alice 持有 $u$ ，Bob 持有 $v$ 。构造如下：

公开抽取公平的 $E=D_{-i}$ ，以及原协议的公共币 $R$ ；新公共币是 $Q_i=(E,R)$ 。
对每个 $j\ne i$ ，若 $E_j=0$ ，Alice 置 $X_j=0$ ，Bob 私下抽公平 $Y_j$ ；若 $E_j=1$ ，Bob 置 $Y_j=0$ ，Alice私下抽公平 $X_j$ 。这些填充币相互独立，也独立于运行原协议的随机带。
置 $X_i=u,Y_i=v$ ，运行原 DISJ 协议。Bob 将输出取反，作为 AND 答案。

其他坐标始终不相交，所以对全部四种 $(u,v)$ ，包括支撑外的 $11$ ，都有 $1-\operatorname{DISJ}_n(X,Y)=u\land v$ 。每个完整输入的错误率至多 $\varepsilon$ ，再平均填充随机性，错误率仍至多 $\varepsilon$ 。

现在才在分析中令 $(U,V,D_i)$ 服从单坐标困难分布。补齐后的 $(D^n,Z^n,R,T)$ 联合分布与原实验完全一致。因此构造协议的单坐标成本恰好是

I(U,V;T_i\mid D_i,Q_i) =I(Z_i;T\mid D^n,R).

真实的 $D_i$ 从未交给协议；填充的公平输入位也没有全部公开，否则观察者拥有的信息会改变。对每个 $i$ 应用刚刚证明的 AND 界，再代入熵直和，就得到 $\operatorname{CIC}(\Pi)\ge nc_\varepsilon$ 。[1]

通信结论与适用边界

固定公共币后，有限协议树的完整消息记录是前缀无歧义编码，故

\operatorname{CIC}(\Pi) \le H(T\mid D^n,R)\le H(T\mid R) \le E|T|\le\operatorname{CC}(\Pi).

发送 Alice 的全部 $n$ 位给出 $n$ 位上界，所以固定 $\varepsilon<1/2$ 时公共币通信复杂度为 $\Theta_\varepsilon(n)$ 。这与Razborov 的矩形腐败路线到达同一通信终点；平滑矩形界以带标签矩形作证，此处用的是条件输入熵和消息分布几何。

因为 $T\perp D^n\mid Z^n,R$ ，链式法则还给出

I(Z^n;T\mid R) =I(D^n;T\mid R)+I(Z^n;T\mid D^n,R) \ge\operatorname{CIC}(\Pi).

所以这里也下界普通外部信息，但这不自动下界普通内部信息。信息等于摊销通信使用匹配的内部信息和分布错误定义，不能仅凭本页条件外部下界就套用：若只要求在上述无交点分布上正确，恒输出一的零通信协议合法，任意多个独立副本也一样。

同样，坐标完全相关时输入熵不能拆成这里的独立和；量子消息、多方 NOF、其他 promise 或无统一深度的协议需要重新核对结构与极限。正文证明的终点是已明确模型下、逐输入正确的二方 DISJ 线性下界。

参考资料

[1] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar, “An Information Statistics Approach to Data Stream and Communication Complexity”, Journal of Computer and System Sciences 68(4), 702–732, 2004。期刊稿：印刷页706的输出约定，§4条件信息，§5 Lemmas5.1/5.5与Theorem5.6，§6因子分解、cut-and-paste和统计距离。原文要求输出由完整记录决定；本文通过同一Bob输入的后验随机带论证，明确处理私有输出，并独立推导所用常数。

形式陈述 ​

一 bit AND：输出恒零，消息仍有信息 ​

两坐标：直和何时严格 ​

单坐标 AND 的完整距离证明 ​

信息如何控制 Hellinger 距离 ​

因子分解如何跨过分布支撑 ​

私有输出如何迫使距离为正 ​

条件熵直和与每个坐标的实际协议 ​

通信结论与适用边界 ​

反向链接