分布通信复杂度

固定分布后的定义 ​

设 $f:X\times Y\to Z$，并固定输入对上的概率分布公理库概率分布Probability distribution · Law定义在可测空间上的概率测度；随机变量的律是由推前得到的一类分布。 $\mu$。确定性协议 $\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。

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

若一条公共币随机协议每次通信至多 $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$。固定随机币不会增加其通信硬上限，于是得到所需确定性分布协议。

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

一个偏向 Equality 的分布 ​

对 ${\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 比例。若下界只对某个 promise 分布成立，随机结论也只适用于相同合法域；不能把分布质量为零的输入重新加入最坏输入集合。

平均错误的边界 ​

平均错误不是“对大多数随机币正确”。本页没有随机币，协议对每个输入要么正确要么错误；$\mu$ 只给错误输入集合赋质量。随机通信复杂度公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。则固定输入后对币取概率，两层随机性的量词次序不同。

平均输入通信也不同于平均错误。一个协议可以在所有输入都正确，却对少数输入发送极长消息；也可以通信恒短但故意放弃低质量输入。完整结论需分别写 ${\mathrm{err}}_{\mu }$ 与 cost 是 max 还是 expectation。

退化分布若只支持一个输入，协议可把其正确答案硬编码为零通信；这不违反任何定义，却通常无法提供 worst-case 下界。所谓 hard distribution 的“难”需要证明，不能由“随机抽输入”四个字自动获得。

参考资料

• 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.