轮数—通信量权衡

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

下界反向证明短消息不能太快缩小候选：轮消除公理库轮消除引理Round elimination lemma · MNSW round elimination在 indexed direct-sum 问题中证明 Alice 的短首消息对未知目标坐标信息很少，从而删去一条消息并交换起始方。把第一条低信息消息替换掉，自归约把剩余协议解释成规模略小的原问题；MNSW 的 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\times 8}$，并令 $h(z)=Az(\mathrm{mod}2)$。Alice 发送两块的 2-bit hash，共 4 bit。Bob 找到首个 hash 不同的 block；若存在，就回传一位标志、1-bit block 索引和自己的完整 8-bit block，共 10 bit，Alice 在该块作字典序比较；若两 hash 都相同，Bob 回传零标志，Alice 判相等。

例如公开矩阵恰投影前两位，$x=1001011011000010$、$y=1001011001011111$。Alice 发 hash 串 $1011$；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$ 过大，$C^{-k}$ 会使固定常数版下界退化；若允许同一轮双方同时消息，模型也不再是上述交替协议。交互协议压缩公理库交互协议压缩Interactive protocol compression · Interactive compression利用 transcript 的内部信息成本模拟交互协议，并区分单次期望通信、轮数损失与多副本摊销极限。可以通过增加交互来减少通信，因而不能把它的通信上界当作固定轮数曲线上的同参数上界。

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

本页与partition bound公理库通信复杂度的 partition boundPartition bound for communication complexity · Communication partition LP bound以带输出标签的矩形分数权重 LP 松弛随机协议，并由其最优值的对数给出一次性通信下界。镜像对照。partition LP 把随机协议压成无顺序的带标签矩形权重，能下界总通信，却忘记矩形按何种 transcript 顺序产生；因此不能单独区分 $R^{(r),A}$ 与 $R^{(r),B}$。反过来，round elimination 依赖自归约，并不普遍支配 one-shot LP。两类证据回答不同资源问题，而非谁对所有函数更强。