通信下界归约范式

反证模板 ​

目标是为模型 $\mathcal{M}$ 中的任务 $Q$ 证明资源下界。先选通信问题 $F(x,y)$，再假设存在资源仅为 $s$ 的 $Q$-算法 $A$。归约必须把它变成通信协议 ${\mathrm{\Pi }}_A$，使 Alice 只用 $x$ 构造自己的对象片段，Bob 只用 $y$ 构造另一片段，并由 $A$ 的输出恢复 $F(x,y)$。

若模拟产生的通信至多 $g(s)$，错误和轮数落在已知通信下界的模型内，而 $F$ 需要至少 $L$ bit，就有

$$g(s)\ge L.$$

随后解出 $s$ 的下界。证明的逻辑是逆否：一个过于节省资源的算法会制造一个不可能的低通信协议。仅说“由通信复杂度可知”没有给出输入编码、模拟过程或参数关系，不能构成归约。

这与多项式时间归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。共享“把一个问题实例映到另一个问题并保持答案”的思想，却关注不同量。通信归约常允许双方免费做很昂贵的本地计算；关键是精确保留空间、pass、probe、适应性和错误，而不只是多项式时间可计算。

五项检查表 ​

第一，局部编码：Alice 构造的部分不能依赖 $y$，Bob 的部分不能依赖 $x$。若编码器偷看完整输入，通信障碍已被绕过。

第二，执行切分：说明算法状态何时从一方控制转到另一方，并逐次列出发送内容。消息必须足以继续模拟，也不能包含模型原本不可访问的日志。

第三，输出解码：给出 $A$ 的精确输出或近似值怎样区分 $F=0$ 与 $F=1$。两类实例的数值区间必须不重叠，不能依靠“通常更大”判断。

第四，概率耦合：固定公共/私有随机性如何映射，证明每个通信输入的错误概率不超过原算法保证。若原保证只对 oblivious 输入成立，归约不能让后半段自适应地读取随机状态后选输入。

第五，参数账本：写出消息 bit 数、轮数、输入规模、word 宽、pass 数和适应性之间的公式。通信定理的每项前提都要在账本中有对应项。

一趟 streaming 的状态消息 ​

设一趟数据流算法公理库数据流算法模型Data-stream model · Streaming algorithm输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。用 $S$ bit 工作状态。归约把流连接为

$$\sigma (x,y)={\sigma }_A(x)\circ {\sigma }_B(y).$$

Alice 从初态处理前缀 ${\sigma }_A(x)$，将完整 $S$-bit 状态发给 Bob；Bob 继续处理 ${\sigma }_B(y)$ 并解码 $F(x,y)$。这是一条 $S$-bit 单向协议，所以若母问题需要 $\mathrm{\Omega }(n)$ bit，就得到 $S=\mathrm{\Omega }(n)$。

若算法有 $p$ 趟，读头在前后片段间往返，状态会跨切口传递 $O(p)$ 次，得到多轮、总通信 $O(pS)$ 的协议。把一趟下界不加修改地用于多趟算法，会漏掉轮数提供的能力；正确结论应匹配相同轮数的通信下界。

线性 sketch 的合并消息 ​

线性 Sketch公理库线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。将频率向量 $v$ 映为 $Av$。Alice 发送 $A{v}_x$，Bob 利用线性性计算

$$A(v_x+v_y)=A{v}_x+A{v}_y$$

并运行解码器。若摘要有 $d$ 个、每个 $w$ bit 的坐标，消息是 $dw$ bit，而不是抽象的“一个向量”。矩阵 $A$ 是公开固定、公共随机选择还是 Alice 私选，也必须与目标通信 coin model 对齐。

若 sketch 只保证对每个固定向量高概率正确，归约要先固定 $(x,y)$ 再对随机矩阵取概率。若 Bob 根据看到的 sketch 自适应构造 $v_y$，最终向量依赖随机性，原保证可能不再适用。

Cell-probe 的交互模拟 ​

在单元探测模型公理库单元探测模型Cell-probe model将内部计算设为免费、只统计对 w 位内存单元读写次数的数据结构复杂度模型。中，可让 Alice 持有由 $x$ 建成的内存表，Bob 持有由 $y$ 决定的查询。一次自适应 probe 时，Bob 发送地址，Alice 返回该 cell 内容；若表有 $S$ 个 cell、每个宽 $w$ bit，一次往返至多使用 $\lceil {\log }_{2}S\rceil +w$ bit。

$t$ 次 probe 形成 $t$ 轮自适应对话，总通信

$$O(t(\log S+w)).$$

后一个地址可依赖先前 cell 内容，协议必须保留这一轮序；把全部地址预先批量发送只适用于非自适应查询。若预处理内存也依赖 Bob 输入，Alice 无法独自持有它，模拟需要重新设计。

失败边界 ​

空间按 machine word 报告时，要乘 word 宽才能成为 bit 消息；状态含随机种子时，要说明种子是共享、隐藏还是实际传输。允许外部只读输入、建议字符串或服务器缓存，也都可能穿过通信切口，不能从账本中消失。

近似算法的阈值必须留出误差余量。例如两类实例真实值相差 $\mathrm{\Delta }$，而算法加性误差可达 $\mathrm{\Delta }$，输出区间会重叠，Bob 无法据此解码通信 bit。成功概率放大还会成倍增加资源，不能只把错误率改小。

最后，一个通信下界只能约束成功归约覆盖的算法族。若归约产生单向协议，它不能调用只对多轮协议成立的下界；若通信母问题有 promise，编码后的每个实例都必须满足 promise。参数守恒是证明本身，不是附录里的实现细节。

参考资料

• Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015, Lectures 4–6.
• David P. Woodruff, “Sketching as a Tool for Numerical Linear Algebra,” Foundations and Trends in Theoretical Computer Science 10(1–2), 2014, Sections 2–3.
• Mihai Pătraşcu and Erik D. Demaine, “Logarithmic Lower Bounds in the Cell-Probe Model,” SIAM Journal on Computing 35(4), 2006, pp. 932–963.