单向通信复杂度 | Codeboy's Blog

形式陈述

单向协议的形式

固定两方模型的有限非空输入与输出集合，并只要求 Bob 输出。在 Alice-to-Bob 的确定性单向协议中，Alice 根据私有输入 $x\in X$ 计算一条消息

m(x)\in\{0,1\}^*,

发送后不再接收 Bob 的任何信息。Bob 持有 $y\in Y$ ，用解码函数 $g$ 输出 $g(m(x),y)$ 。协议计算 $f:X\times Y\to Z$ ，当且仅当对所有 $(x,y)$ 都有

g(m(x),y)=f(x,y).

若消息固定为 $c$ bit，确定性单向复杂度 $D^{\rightarrow}(f)$ 是所有正确编码器—解码器对中最小的 $c$ 。变长消息也可以研究，但必须采用可自定界编码并对最坏消息长度计费，不能把终止时间当作额外免费信息。

随机单向协议允许编码器、解码器使用模型声明的随机币，并要求对每个固定 $(x,y)$ ，错误概率至多 $\varepsilon$ 。相应复杂度常写作 $R^{\rightarrow}_\varepsilon(f)$ 。公共币还是私有币、通信硬上限还是期望长度，都会改变精确定义；只写一个箭头不能替代这些口径。

函数行刻画

Alice 发送消息时看不到 $y$ ，所以同一 $m(x)$ 必须支持 Bob 随后面对每个可能的 $y$ 。两个 Alice 输入 $x,x'$ 可以安全地使用同一消息，当且仅当它们对 Bob 的全部输入都诱导相同输出：

\forall y\in Y,\qquad f(x,y)=f(x',y).

若存在某个 $y$ 让两者输出不同，Bob 在收到相同消息、持有该 $y$ 时便无法正确区分。因此确定性单向协议实质上把 $X$ 按函数行 $f(x,\cdot)$ 的相等关系编码；不同的行行为需要不同消息。

形式上可定义 $x\sim_f x'$ 当且仅当对所有 $y$ 都有 $f(x,y)=f(x',y)$ 。正确确定性消息必须把不同等价类分开；反过来，若 Alice 发送自己所属等价类的索引，Bob 就能由该类的共同函数行回答。

因此若共有 $N_f$ 个不同函数行，固定长度消息需要且只需 $\lceil\log_2N_f\rceil$ bit。这个等式描述的是无限本地计算下的最优编码；求等价类或存储完整函数行是否可行，仍不在单向通信度量内。

对关系问题，简单的“函数行相等”条件要改成解码可行性：同一消息类中的所有 $x$ ，对每个固定 $y$ 都必须存在一个 Bob 可输出、且对该类全部输入同时合法的答案。逐个输入各有某个合法答案，并不足以让 Bob 在不知道 $x$ 时选择同一个答案。

直觉

消息不是对 $x$ 的通用压缩，而是一份面向所有 Bob 输入的摘要。Alice 发信时不知道 $y$ ，同一编码必须让 Bob 在每个可能的后续情境中都能回答；只要两个 $x$ 在某一列产生不同输出，它们就不能安全碰撞。

这也解释了方向为何重要。Alice-to-Bob 区分函数矩阵的行，Bob-to-Alice 区分列；反馈则让发送者先得知对方真正关心的问题，再定制回答。看似只改变箭头或轮数，实质上改变了消息必须同时服务多少种未来。

例子与边界

单向模型允许 Alice 的消息直接到达 Bob，Bob 可结合自己的输入输出；同时消息传递模型要求 Alice 与 Bob 互不见对方消息，只把各自摘要发给 referee。缺少接收方反馈和直接通信会改变协议可表达的信息组合。

一个索引访问的执行图像

令 Alice 持有 $x=x_1\cdots x_n\in\{0,1\}^n$ ，Bob 持有索引 $i\in\{1,\ldots,n\}$ ，目标输出 $x_i$ 。Alice-to-Bob 的朴素协议把整个 $x$ 作为 $n$ -bit 消息；Bob 收到后读取第 $i$ 位。对输入 $x=10110$ 、 $i=4$ ，通信 transcript 就是 10110，Bob 输出 $1$ 。

若交换允许的方向，让 Bob 先发送 $i$ ，Alice 只需回传 $x_i$ 。索引编码使用 $\lceil\log_2 n\rceil$ bit，再加一 bit 回答；这已经不再是 Alice-to-Bob 的单向协议，而是另一方向加回复的两轮协议。

函数行刻画还能补全最优性：每两个不同串 $x,x'$ 总在某坐标 $i$ 不同，所以 Index 共有 $2^n$ 个不同函数行，确定性 Alice-to-Bob 单向复杂度恰为 $n$ 。有界错误随机单向 Index 对固定 $\varepsilon<1/2$ 仍有 $\Omega(n)$ 下界，但这需要随机编码下界，不能仅靠确定性碰撞计数推出。反馈则把“摘要全部可能问题”改成“回答一个已经公开的问题”。

边界与比较

若一般两方模型也只要求 Bob 输出，每个 Alice-to-Bob 单向协议都是其特例，所以交互复杂度不大于同口径的单向复杂度。若一般模型要求输出成为公开叶标签，则 Bob 还需回传输出编码，至多多出 $\lceil\log_2|Z|\rceil$ bit。反过来仍不成立：单向下界只排除没有反馈的消息结构，不能自动排除双方交替询问的协议。

消息长度按 bit 计。若消息符号有 $M$ 种可能，固定长度编码需要至少 $\lceil\log_2M\rceil$ 位来区分它们。公共随机串若由模型免费共享，就不计入消息长度；由它选出的哈希函数所产生的哈希值，仍须实际发送。

单向模型不限制 Alice 生成 $m(x)$ 的时间，也不限制 Bob 解码的时间。一个存在性编码可能要枚举全部输入才能求出；它给出通信上界，却未必给出高效 sketch 或数据结构。将通信结果迁回算法时，计算可实现性需要单独验证。

推论与应用

数据流状态为何形成单向消息

考虑一个使用 $S$ bit 状态的一趟数据流算法。把流切成前缀 $\sigma_A$ 与后缀 $\sigma_B$ ：Alice 在前缀上运行算法，将当前状态 $s(\sigma_A)$ 发给 Bob；Bob 从该状态继续处理后缀并输出。这里发送的是完整可续跑配置，包括必须继承的私有种子与计数器；Bob 可继续抽取独立新币，过去已耗用且不会复用的随机位无需发送。若种子是模型允许免费共享的输入无关参数，则双方直接共享它。按此计费就得到一条至多 $S$ bit 的单向消息。

这条转换保留的是“前缀处理完后唯一流向后缀的信息”。如果 streaming 算法有 $p$ 趟，状态会在切口来回传递，对应多轮协议，而不是仍然一条单向消息；如果算法把完整前缀写入未计费外部日志，消息也不再只有 $S$ bit。下界归约必须逐项保存这些资源条件。

归约方向是“假设有小空间算法，构造小通信协议，再与通信下界矛盾”。因此通信困难推出空间困难，而一条通信上界并不自动给流算法：通信双方的本地计算免费，也可能一次访问完整输入，流算法却只有有限状态且只能按到达次序读数据。

固定长度的 INDEX 流式归约把这一接口完整落地：Alice 插入 $n$ 个键 $(j,x_j)$ ，Bob 追加 $(i,1)$ ，由不同元素数 $n+1-x_i$ 恢复答案。前缀状态必须在 $i$ 尚未揭示时形成，因此精确单遍计数继承随机 INDEX 的线性 bit 下界。该页的两遍算法则先记住最后键、再扫描前缀，展示反馈与重读怎样越出一次消息的能力限制。

线性摘要和分布式聚合也常有同一形状：Alice 发送 sketch，Bob 加入自己的更新后解码。能合并不表示消息无损；近似误差、失败概率与随机种子可见性必须随摘要一起带进通信协议。

不同函数行的精确计数给出确定性单向复杂度的完整刻画；在随机协议中，这种“完全分开”会放宽为用短随机消息近似区分行分布。Indexing、Equality 与 streaming sketch 的差异，正可从 Bob 需要恢复的是任意坐标、相等性判定还是近似统计量来理解。

参考资料

Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Sections 1.3 and 3.2.
Tim Roughgarden, Communication Complexity (for Algorithm Designers), Stanford CS369E, 2015，Lecture 2: Lower Bounds for One-Way Communication，§2（pp. 3–4）的随机性定义与 §4 的 INDEX 下界；合订讲义对应 §2.4。
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 2 and 4.

形式陈述 ​

单向协议的形式 ​

函数行刻画 ​

一个索引访问的执行图像 ​

边界与比较 ​

数据流状态为何形成单向消息 ​