交互协议压缩

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

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

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

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

本页结果不是“任意协议可通信到恰好 $I$ 且不改 round”的定理。单次、最坏通信、极小模拟误差和 round-preserving 四个目标之间存在真实损失；这正是它与轮数—通信量权衡公理库轮数—通信量权衡Round-communication tradeoff · Round-sensitive communication complexity固定消息条数、首发者、单消息预算与错误后，刻画增加交互如何降低完成同一通信任务的总 bit 数。的边界，后者固定消息条数后再问最少通信。多副本典型序列会把这些次线性开销摊薄，才得到精确的摊销等式公理库摊销通信复杂度Amortized communication complexity · Information equals amortized communication以乘积分布上多副本单位通信极限定义摊销量，并精确陈述其等于内部信息复杂度。。

把 $n$ 份协议并行模拟，信息主项为 $nI$，而典型性与容错开销可取 $o(n)$，由此得到 information equals amortized communication。对首消息只含 $a/m$ 平均信息的 direct-sum 型问题，同一低信息模拟思想还可让接收方公开采样该消息并删除一轮；轮消除公理库轮消除引理Round elimination lemma · MNSW round elimination在 indexed direct-sum 问题中证明 Alice 的短首消息对未知目标坐标信息很少，从而删去一条消息并交换起始方。页只使用这个特化步骤，不把完整交互压缩当作历史上的 MNSW 前置。

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