随机通信复杂度

随机性放在协议哪里 ​

在两方通信模型公理库两方通信模型Two-party communication model · Two-party communication complexity model两位参与者各自持有私有输入，只以交换消息协同计算函数或关系，并把通信位数作为核心资源。上加入随机币，得到随机协议 $\mathrm{\Pi }(x,y;R_A,R_B)$，其中 $R_A,R_B$ 是双方的私有随机币。它与确定性协议是同一基础模型上的平行变体，不以“确定性通信复杂度”这个度量为构造前置。给定 $(x,y)$ 与两条随机带后，协议变成确定性消息过程，产生 transcript、输出和通信量。随机性不会改变输入，也不会让一方直接看见另一方的私有币。

本页以私有币、双侧误差和最坏通信硬上限为基线。协议以误差 $\epsilon$ 计算 $f$，若对每个固定输入对都有

$${\text{Pr}}_{R_A,R_B}[\mathrm{\Pi }(x,y;R_A,R_B)\ne f(x,y)]\le \epsilon .$$

在每次随机选择都发送至多 $c$ bit 的协议中取最小 $c$，得到 $R_{\epsilon }^{\mathrm{cc},\mathrm{priv}}(f)$。通常在上下文已经固定 coin model 后简写为 $R_{\epsilon }^{\mathrm{cc}}(f)$；若同时讨论查询复杂度，保留上标可避免与其 $R_{\epsilon }(f)$ 混淆。

随机化算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。的基本量词在这里仍然有效：先固定输入，再对内部随机性取概率。把输入也按某个分布抽样并只控制平均错误，会得到另一个分布模型，不能替代上述逐输入保证。

通信成本有两种常用口径 ​

硬上限口径要求

$$\underset{x,y,r_A,r_B}{max}{c}_{\mathrm{\Pi }}(x,y;r_A,r_B)\le c.$$

期望通信口径则可能要求 $\underset{x,y}{max}{\mathbb{E}}_R[c_{\mathrm{\Pi }}(x,y;R)]\le c$。后者允许极少数随机带产生很长 transcript，前者不允许。即使二者最后都写成 $O(g(n))$，保证仍不相同。

还有一个容易误换的式子：

$$\underset{x,y}{max}{\mathbb{E}}_R[c_{\mathrm{\Pi }}(x,y;R)]\text{与}{\mathbb{E}}_R[\underset{x,y}{max}{c}_{\mathrm{\Pi }}(x,y;R)].$$

第一式允许每条随机带的坏输入不同，第二式则对每次固定随机选择都寻找最坏输入，通常更强。比较文献结论时，必须先对齐通信成本和错误概率各自的量词。

一个带 gap 的随机协议 ​

考虑 promise 问题：Alice 与 Bob 各持 $n$ bit 串，合法输入要么满足 $x=y$，要么满足 $d_H(x,y)\ge n/3$；目标区分这两种情形。Alice 私下均匀抽取坐标 $I\in \{1,\dots ,n\}$，向 Bob 发送 $I$ 的编码和 bit $x_I$。Bob 比较它与 $y_I$，不同就拒绝，相同则暂时接受。

当 $x=y$ 时，任何随机坐标都一致，协议从不误拒。若两串至少三分之一坐标不同，一次抽样漏掉差异的概率至多 $2/3$。独立重复 $k$ 次，并且只有全部坐标都相同才接受，坏输入的误收概率至多

$${\left(\frac{2}{3}\right)}^k.$$

通信量为 $k(\lceil {\log }_{2}n\rceil +1)$ bit。每轮中 Alice 发送抽到的索引，所以协议没有假装双方免费共享她的私有随机选择；Bob 无需随机币也能验证收到的位置。

这个例子的 promise 是保证的核心，而不是装饰。去掉 $n/3$ 的距离下界后，两串可能只差一个坐标，一次抽样发现差异的概率仅为 $1/n$；固定常数次重复几乎总会漏掉。把 gap 例子的错误界直接写成普通 Equality 协议，会把一个错误算法包装成随机化优势。

固定随机币与协议树 ​

固定 $(r_A,r_B)$ 后，随机协议确实成为一棵确定性协议树公理库协议树与通信 transcriptProtocol tree · Communication transcript用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。。但这棵树不必在所有输入上正确。逐输入误差界只说明：对每个 $(x,y)$，使该输入走向错误叶的随机币集合概率至多 $\epsilon$。

量词交换是无效推理的常见来源。由“每个输入各有至少 $1-\epsilon$ 比例的好随机币”，不能推出“存在同一条随机带，对全部输入同时正确”。输入数巨大时，各输入的坏随机币集合可以覆盖整个随机空间。若真找到一条对所有输入都正确的固定随机带，那会给出确定性协议公理库确定性通信复杂度Deterministic communication complexity在零误差确定性协议中，对所有输入的最坏通信位数取最优所得的复杂度度量。，是远强于 bounded-error 定义的结论。

公共随机币允许双方在通信前看见同一随机串；私有随机币则分别隐藏。两种模型及其转换需要单独记录共享性和额外消息，本页不把它们压成“都有随机数”的同一协议。无论哪种模型，公共串本身不计通信并不意味着它携带输入信息：它必须在看到 $x,y$ 之前独立产生。

错误类型与放大边界 ​

双侧误差允许两类输入都以小概率答错；单侧误差要求其中一类永不出错；零误差协议则每次输出都正确，但运行时间或通信量可以成为随机变量。多数表决适合具有固定成功偏差的双侧错误，单侧协议常用 OR 或 AND 聚合保留永不出错的一侧。聚合规则必须与错误结构匹配。

概率放大还要求各次试验拥有足够独立的随机性。机械重复同一随机种子不会把错误概率从 $\epsilon$ 变成 ${\epsilon }^k$，它只把同一错误决定复制 $k$ 次。重复也按比例增加通信；不能只更新成功概率而保留原消息长度。

最后，随机通信上界仍在免费本地计算模型中。用一个信息论上存在但难以求值的随机编码，不能自动得到高效分布式算法；而在这种强模型中成立的通信下界，才可作为其他受限模型的稳健障碍。

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapter 3.
• Ilan Newman, “Private vs. Common Random Bits in Communication Complexity,” Information Processing Letters 39(2), 1991, pp. 67–71.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 3–4.