轮数—通信量权衡 | Codeboy's Blog

形式陈述

固定有限非空输入上的函数 $f$ 、输出者约定、整数 $r\ge1$ 与 $0\le\varepsilon<1/2$ 。定义 $R^{(r),A}_\varepsilon(f)$ 为公共币随机协议中逐输入错误至多 $\varepsilon$ 、至多发送 $r$ 条交替消息且 Alice 先说的最小最坏总通信量； $R^{(r),B}$ 对称。显然

R^{(r+1),A}_\varepsilon(f)\le R^{(r),A}_\varepsilon(f),

但有意义的 tradeoff 要给随 $r$ 变化的定量上下界，并说明是否限制每方每条消息长度。输出可以指定一方，也可以要求双方都知道；以下每个例子明确选择，不能在比较中切换。

指针追逐给出一组经典上下界。对 $n\ge2$ 、 $k\ge2$ 的 $g_k$ ，要求双方知道答案，Bob 首发且至多 $k$ 条消息，有

\Omega\!\left(\frac{n}{k^2}-k\log n\right) \le R^{(k),B}_{1/3}(g_k) \le O\!\left((k+\tfrac nk)\log n\right),

而让知道首指针的 Alice 首发只需 $O(k\log n)$ 。当 $k\le\sqrt n$ 时，上界可简化为 $O((n/k)\log n)$ ；Bob 首发的 $k=1$ 情形无法完成双方输出任务。原文对随机种子平均的成本下界也适用于这里的硬上限，而所引抽样协议本身具有硬上限。这里同时固定消息数、方向与输出要求，不能用不限制轮数的 $R_{1/3}(g_k)$ 代替。

另一完整版本来自 Greater-Than。轮消除引理的逐步应用取 $C=99,R=4256$ ，对 $n$ 位严格比较、逐输入错误至多 $1/3$ 、至多 $k$ 条消息和每条至多整数 $c\ge1$ bit，证明

n<(Rc)^kC^{k(k-1)/2}, \qquad c>\frac{n^{1/k}}{R C^{(k-1)/2}}.

这里 $k$ 数消息，且允许预先固定任一方输出；取整、角色变换和每步错误预算都在证明中保留。固定 $k$ 时得到 $\Omega_k(n^{1/k})$ ，对增长的 $k$ 则须保留常数的衰减。对固定 $k$ ，由最后一条消息的接收者输出的递归比较协议，用 $k$ 条消息和 $O_k(n^{1/k}\log n)$ 总 bit 完成任务，展示更多交互如何逐步定位首次不同 bit。下面的两消息实例因而由 Alice 输出。

直觉

一条长消息必须一次覆盖许多尚未知的对方分支；多轮协议可以让后一条消息只回答前一条已经缩小的候选集。Greater-Than 每轮缩小共同前缀区间，pointer chasing 每轮揭示下一地址。round 越多，适应性越强，总 bit 可下降。

下界反向证明短消息不能太快缩小候选：轮消除把第一条低信息消息替换掉，自归约把剩余协议解释成规模略小的原问题；上述 Greater-Than 下界正直接调用这套迭代。到零轮时若问题仍有两个不同答案，就得到矛盾。每次规模缩减和消息预算放大共同决定最终的 $n^{1/k}$ 曲线；pointer chasing 的 $n/k^2$ 则来自 Nisan–Wigderson 针对路径分布的专门分析，不把两种证明冒充为同一条引理。

例子与边界

对 $n=16$ bit 的 Greater-Than，给一条真实的两消息 public-coin 轨迹，只要求 Alice 输出。把输入分成高、低两个 8-bit block；公共币抽取随机二进制矩阵 $A\in\{0,1\}^{2\times8}$ ，并令 $h(z)=Az\pmod2$ 。Alice 发送两块的 2-bit hash，共 4 bit。Bob 找到首个 hash 不同的 block；若存在，就回传一位标志、1-bit block 索引和自己的完整 8-bit block，共 10 bit，Alice 在该块作字典序比较；若两 hash 都相同，Bob 回传零标志，Alice 判相等。

例如公开矩阵恰投影前两位， $x=10010110\,11000010$ 、 $y=10010110\,01011111$ 。Alice 发 hash 串 $10\,11$ ；Bob 看到高块 hash 相同、低块为 $01$ ，回传“低块”和 $01011111$ ，Alice 由 $11000010>01011111$ 正确判 $x>y$ 。对任意固定不同的 8-bit 块，随机 $A$ 使二者碰撞的概率为 $2^{-2}=1/4$ ；只要真实首个不同块不碰撞，Bob 找到的就是决定答案的块，所以逐输入错误至多 $1/4$ ，最坏通信 14 bit。一般化为更多 block 并递归可得到 round/communication 曲线；该轨迹解释上界结构，不替代 MNSW 下界。

tradeoff 必须固定“轮”是消息数还是一对往返、允许谁先说、最后谁输出、通信是期望还是硬上限。若 $k$ 随 $n$ 过大， $1/(R C^{(k-1)/2})$ 会使本页下界退化；若允许同一轮双方同时消息，模型也不再是上述交替协议。交互协议压缩可以通过增加交互来减少通信，因而不能把它的通信上界当作固定轮数曲线上的同参数上界。

推论与应用

round-sensitive 下界可转移到 cell-probe：查询者消息编码地址，存储者回复 cell 内容，一次 probe 对应一对消息；于是通信 tradeoff 同时限制 probe 数、地址长度和 word size。它也解释 streaming 多 pass 为什么可能用更少空间：每次 pass 提供一次新的适应性交互。

本页与partition bound镜像对照。partition LP 把随机协议压成无顺序的带标签矩形权重，能下界总通信，却忘记矩形按何种 transcript 顺序产生；因此不能单独区分 $R^{(r),A}$ 与 $R^{(r),B}$ 。反过来，round elimination 依赖自归约，并不普遍支配 one-shot LP。两类证据回答不同资源问题，而非谁对所有函数更强。

参考资料

Noam Nisan and Avi Wigderson, “Rounds in Communication Complexity Revisited,” SIAM Journal on Computing 22(1), 1993, pp. 211–219.
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson, “On Data Structures and Asymmetric Communication Complexity,” Journal of Computer and System Sciences 57(1), 1998, pp. 37–49.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 3 and 6.

形式陈述 ​

反向链接

形式陈述