交互协议压缩 | Codeboy's Blog

长 transcript 的逐轮信息成本经相关采样转成更短的模拟通信 — 交互协议按信息成本压缩

形式陈述

固定有限输入分布 $\mu$ 与整数 $k\ge1$ 。设允许公共币和独立私有币的有限协议 $\pi$ 至多交换 $k$ 条消息，transcript 为 $T$ ，其有限内部信息成本为

I=I(X;T\mid Y,R)+I(Y;T\mid X,R).

Braverman–Rao 的单次模拟给出：对任意 $0<\delta<1/k$ ，存在交互协议 $\tau$ ，双方输出一份 $\pi$ 的 transcript；存在事件 $G$ ， $\Pr[G]>1-k\delta$ ，使条件于 $G$ 时双方输出相同且分布精确等于原 transcript，并且条件期望通信至多

I+O(\sqrt{kI}+k)+2k\log_2(1/\delta).

这是分布意义下、成功事件上的条件期望通信界。令上式右端的一个有效上界为 $B$ ，实际通信量为 $C$ 。在整数预算 $L\ge1$ 处截断，用条件版本的Markov 不等式可得额外失败总概率至多 $k\delta+B/L$ ，因为 $\Pr(G\cap\{C>L\})\le\Pr(C>L\mid G)\le B/L$ 。不能直接把 $B$ 当成无条件的 $E[C]$ 。若要保持原 round 数，模拟协议的交互安排还需另行核对。

核心一步是单消息 correlated sampling。Alice 发送消息时，她知道 $P=\mathcal L(M\mid X=x,T_{<t},R)$ ，Bob 知道 $Q=\mathcal L(M\mid Y=y,T_{<t},R)$ ；Bob 发送时交换两方角色。固定有限消息集合，发送方输出的样本 $a$ 精确服从 $P$ ，接收方输出 $b$ ，并对每个 $P(u)>0$ 的 $u$ 保证 $\Pr[b=u\mid a=u]>1-\delta$ 。公开模拟随机性配合逐步哈希，使期望通信至多

D_{\mathrm{KL}}(P\|Q)+2\log_2(1/\delta)+O(\sqrt{D_{\mathrm{KL}}(P\|Q)+1})

bit；这里用以二为底的KL 散度，有限界要求 $P\ll Q$ 。逐消息再对原协议的上下文取平均，所得 KL 散度之和正是内部信息成本。公开模拟币是额外的共同资源，不意味着把原私有随机带交给对方。

直觉

通信 transcript 可能很长，却只让双方学到很少新信息：大量 bit 可由接收方侧信息预测。压缩器不发送整条消息，而是帮助接收方从自己的条件分布 $Q$ 校准到发送方的 $P$ ；二者越接近，所需哈希证据越短。

交互的难点是误差和上下文会逐轮累积。第 $t$ 轮的条件分布依赖此前模拟出的 transcript，单轮成功并不自动保证整条轨迹正确；这解释了公式中的 $k\delta$ 、 $\sqrt{kI}$ 和逐轮对数项。

例子与边界

令宇宙 $U=\{1,\ldots,8\}$ 。Alice 知道 $P$ 为 $\{1,2\}$ 上均匀分布，Bob 的先验 $Q$ 为 $U$ 上均匀分布。对 $x\in\{1,2\}$ ， $P(x)/Q(x)=4$ ，故

D_{\mathrm{KL}}(P\|Q) =\sum_{x=1}^2\frac12\log_2 4=2.

双方从公开随机序列找候选，再由 Alice 发送哈希 bit 排除 Bob 额外的六个候选；信息主项恰为两 bit，而直接发送 $U$ 中索引需三 bit。若 $P$ 把正质量放在 $Q$ 的零质量点上，KL divergence 为无穷，该保证正确地不给有限压缩承诺。

本页结果不是“任意协议可通信到恰好 $I$ 且不改 round”的定理。单次、最坏通信、极小模拟误差和 round-preserving 四个目标之间存在真实损失；这正是它与轮数—通信量权衡的边界，后者固定消息条数后再问最少通信。多副本典型序列会把这些次线性开销摊薄，才得到精确的摊销等式。

推论与应用

把 $n$ 份协议并行模拟，信息主项为 $nI$ ，而典型性与容错开销可取 $o(n)$ ，由此得到 information equals amortized communication。对首消息只含 $a/m$ 平均信息的 direct-sum 型问题，同一低信息模拟思想还可让接收方公开采样该消息并删除一轮；轮消除页只使用这个特化步骤，不把完整交互压缩当作历史上的 MNSW 前置。

压缩是上界工具，不会自行证明某函数的信息成本大。若输入分布改变，条件分布和 KL 账本也改变；若协议用 private coins，可把公开模拟随机性与原私币分开表示，但不能免费共享原本隐藏的随机带。

参考资料

Mark Braverman and Anup Rao, “Information Equals Amortized Communication,” IEEE Transactions on Information Theory 60(10), 2014, pp. 6058–6069。作者稿 Theorem 2.1、Corollary 2.2 与 §6.1 分别说明单消息采样、成功事件上的条件期望界及逐轮组合。
Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao, “How to Compress Interactive Communication,” Proceedings of STOC, 2010, pp. 67–76.
Mark Braverman, “Interactive Information Complexity,” Proceedings of STOC, 2012, pp. 505–524.

形式陈述 ​

反向链接

形式陈述