分布通信复杂度

形式陈述 ​

固定分布后的定义 ​

设 $X,Y,Z$ 有限非空，$f:X\times Y\to Z$，并固定输入对上的概率分布公理库概率分布Probability distribution · Law可测空间上总质量为一的测度；随机变量的律是由样本概率推出的一类分布。 $\mu$。确定性协议公理库确定性通信复杂度Deterministic communication complexity在零误差确定性协议中，对所有输入的最坏通信位数取最优所得的复杂度度量。 $\mathrm{\Pi }$ 的分布错误为

$${\mathrm{err}}_{\mu }(\mathrm{\Pi },f)={\text{Pr}}_{(x,y)\sim \mu }[\mathrm{\Pi }(x,y)\ne f(x,y)].$$

在最坏通信硬上限至多 $c$、且 $\mu$-错误至多 $\epsilon$ 的确定性协议中取最小 $c$，定义

$$D_{\epsilon }^{\mu }(f)=\underset{\mathrm{\Pi }:{\mathrm{err}}_{\mu }(\mathrm{\Pi },f)\le \epsilon }{min}\underset{x,y}{max}{c}_{\mathrm{\Pi }}(x,y).$$

协议是确定性的，概率只来自输入分布。允许它在一小块 $\mu$-质量上完全错误，却仍对其通信取所有输入的硬上限；若同时只计期望通信 ${\mathbb{E}}_{\mu }[c_{\mathrm{\Pi }}]$，那是另一个 distributional cost convention。

承诺域与未计分的输入 ​

对 $f:X\times Y\to Z\cup \{\ast \}$，令 $D=\mathrm{dom}f$。通常取 $\mu (D)=1$。有些矩形下界还允许 $\mu$ 在承诺外有质量；此时采用未条件化的错误

$${\mathrm{err}}_{\mu }(\mathrm{\Pi },f)={\text{Pr}}_{(x,y)\sim \mu }[(x,y)\in D\wedge \mathrm{\Pi }(x,y)\ne f(x,y)].$$

$D_{\epsilon }^{\mu }(f)$ 仍最小化全输入空间的通信硬上限，承诺外输出不计错。若改为先条件化到 $D$ 再测错误，且 $\mu (D)>0$，误差值会除以 $\mu (D)$，所以两种记账不能无声互换。这个约定与 Chakrabarti–Regev 的§2.1一致，也保留下文固定随机币的平均论证。

与最坏输入随机协议的一侧关系 ​

若一条公共币随机协议公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。每次通信至多 $c$，且对每个固定输入错误至多 $\epsilon$，那么对任意固定 $\mu$ 都有

$$D_{\epsilon }^{\mu }(f)\le c.$$

证明只需展开期望。令 $E(x,y,r)$ 为错误指示量，则

$${\mathbb{E}}_R{\text{Pr}}_{(x,y)\sim \mu }[E(x,y,R)=1]={\mathbb{E}}_{(x,y)\sim \mu }{\text{Pr}}_R[E(x,y,R)=1]\le \epsilon .$$

因此至少存在一条固定公共随机串 $r^{\ast }$，使确定性协议 ${\mathrm{\Pi }}_{r^{\ast }}$ 的 $\mu$-平均错误至多 $\epsilon$。固定随机币不会增加其通信硬上限，于是得到所需确定性分布协议。

注意固定出的 $r^{\ast }$ 可以依赖 $\mu$：对另一输入分布，可能要选另一条随机带。它也可能在某个输入上必错，只是这些输入在当前 $\mu$ 下质量不超过 $\epsilon$。所以这一步不能把随机协议变成逐输入正确的确定性协议。

这只是从 worst-case randomized 到任意固定分布的方向。反向要把“每个分布各有一条好确定性协议”统一成“一条随机协议对每个输入都好”，涉及极小极大量词交换；不能从本页平均公式直接倒读出来。

直觉

可以把 $\mu$ 看成给输入矩阵的每个格子赋予权重。协议仍对每个格子作出确定回答，但允许回答错误的格子合计重量不超过 $\epsilon$。本页的成本却按最长通信路径收费：少数低权重格子可以被答错，并不意味着可以在这些格子上免费发送长消息。

例子与边界

一个偏向 Equality 的分布 ​

对 $n\ge 1$ 的 ${\mathrm{EQ}}_n$，构造分布 $\mu$：先均匀抽 $x$；以概率 $0.99$ 令 $y=x$，以概率 $0.01$ 从不等于 $x$ 的串中均匀抽 $y$。零通信协议始终输出 $1$，只在后一事件出错，所以

$$D_{0.01}^{\mu }({\mathrm{EQ}}_n)=0.$$

同一函数的最坏输入确定性复杂度仍为线性，因为协议必须正确处理每个不等输入。这个例子不是说 Equality 在分布模型中总是容易，而是说明 $D_{\epsilon }^{\mu }$ 的数值由明确的 $\mu$ 决定；改变 off-diagonal 质量或降低允许错误会改变结论。

若只写“输入通常相等”，却不给概率和条件分布，常数协议的错误率无法复核。分布还可以让 $x,y$ 相关；$\mu$ 不必是边缘分布的乘积，笛卡尔输入空间也不自动意味着独立。

Hard distribution 的证明任务 ​

要用分布复杂度证明随机下界，通常寻找一个 $\mu$，使每条通信少于 $c$ 的确定性协议都有

$${\mathrm{err}}_{\mu }(\mathrm{\Pi },f)>\epsilon .$$

这是一条对 所有 低通信确定性协议的陈述。展示一个输入使某条协议失败不够；分布必须同时让整个协议类无法把错误集中到低质量区域。

困难分布常带相关结构或 promise，以控制每个 transcript 矩形看到的 0/1 比例。这里下界的方向是：若承诺域 $D$ 上已经需要 $c$ bit，那么任何在更大域上计算同一函数的协议，限制到 $D$ 后仍须花费至少 $c$ bit。因此承诺问题的下界可以推出全问题下界，分布在其他输入上质量为零并不妨碍这一推论。

相反，承诺域上的算法上界不能直接延伸到全问题。比如 Equality 的分布若只支持对角输入，常数输出 $1$ 已完全正确；加入不等输入后该协议就可能出错。困难分布既不必支持所有输入，也不能只因为支持较少就被当成容易：关键是其支撑内是否仍让所有小协议失败。

推论与应用

选择困难分布时，首先要排除“把高概率答案直接猜出来”的捷径，再检查低通信 transcript 能隔离哪些输入。例如一个标签占据至少 $1-\epsilon$ 的总质量时，恒输出该标签已满足错误目标，因而不可能从这份分布得到正的 $D_{\epsilon }^{\mu }$ 下界。若标签质量足够均衡，还须继续证明小矩形无法有效分开它们；仅有总体平衡也不保证通信困难。

参考资料

• Eric Blais, “Minimax Principle”, University of Waterloo, CS 860, Winter 2025；固定随机币与分布下界的量词。
• Andrew Chi-Chih Yao, “Probabilistic Computations: Toward a Unified Measure of Complexity,” FOCS, 1977, pp. 222–227.
• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Section 3.3.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 3.