通信下界归约范式

前缀的每一项会留下一个选择，后缀才揭示其中哪个选择重要。如果算法不知道最后会追问哪个位置，那么处理完前缀留下的状态必须足以应付任意后缀。通信模型把这一义务显露出来：Alice 看见选择，却不知道问题；Bob 知道问题，却只能读取 Alice 留下的状态。

图中两种后缀是两个独立固定输入实例，每次执行只发送一次状态。它们共享前缀与消息规则，不是在一次协议里让 Bob 连续追问两个索引。例子的公开参数为 $U=10$、$m=6$。

第一步：用键对编码所有位串 ​

从INDEX 问题公理库Indexing 通信问题Indexing communication problem · INDEX problemAlice 持有 n-bit 串、Bob 持有索引并要恢复对应 bit 的单向通信问题，是流式与摘要空间下界的标准母问题。出发：Alice 持有任意 $x\in \{0,1{\}}^n$，Bob 持有任意 $i\in [n]$，目标输出 $x_i$。定义键宇宙 $[n]\times \{0,1\}$，需要整数键时，用

编码。Alice 构造前缀，Bob 构造一个元素的后缀：

第一坐标不同保证前缀全异，最后键已出现当且仅当 $x_i=1$，所以

Bob 由输出 $Y$ 解码 $x_i=n+1-Y$。若任务直接输出重复谓词，这个谓词就是 $x_i$；若输出“全异”，则要取补。

这里前缀不依赖 $i$，后缀不依赖 $x$。每项都是增量 $+1$，因而也是 strict turnstile 和 general turnstile 模型中的合法输入。所有 $2^n$ 个位串和 $n$ 个索引都保留，没有通过小码本 promise 减轻 INDEX。公开 $n,U,m$ 也不泄露 $x$：无论位串中有多少个 1，前缀恒长 $n$，整条流恒长 $n+1$。

第二步：交接完整状态 ​

假设存在符合上述保证的单遍流算法公理库数据流算法模型Data-stream model输入顺序到达且不能保存全文，以扫描趟数、工作空间、处理时间和输出保证评价算法。 $A$。Alice 从公开初态运行 $A$，依次处理自己的 $n$ 项，在切口得到实际配置 $q_n$。她用固定 $S$-bit 编码发送这个配置；Bob 装载它，继续处理 $(i,1)$，再执行终点解码。这就得到一条 Alice 到 Bob 的单向消息公理库单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。。

“完整”意味着凡是会影响后续运行的工作内存、计数器、持久种子和控制状态都已交接。切口位置恰为公开的 $n$，无需另发位置。若所用机器模型将常数大小的程序控制视为免费，消息长度写作 $S+O(1)$，不影响线性下界。不能只发送主数组，却让 Bob 继续使用未计费的历史日志；也不能把随机状态替换成状态的期望或一个无限精度实数。

对于普通私有币算法，Alice 使用前缀阶段的随机币，Bob 续跑时抽取独立新币。已经消耗、未来不再访问的随机位无需发送；曾抽取而以后还要复用的 seed 必须保存在状态内并计费。如果模型允许输入无关的公开随机函数，双方可免费共享它，这对应公共币协议。由 $x$ 选择的函数或种子包含输入信息，不能因此被算作免费公共参数。

同样，fresh coins 模型不能暗中附带可重读的私有随机带。如果实现需要重新读取过去的带或延续数据依赖的读取位置，那么这些信息必须由公开资源确定，或包含在配置中。对仅使用新币的算法，也可以给初始化、每次更新及终点解码分配独立公开随机块；本例切口编号固定为 $n$，双方可对齐后续随机块。公共币 INDEX 下界已经允许这项额外能力，所以私有币不会成为逃避下界的理由。

第三步：保留逐输入错误并应用 INDEX 下界 ​

先固定任意 $(x,i)$，它确定的整条流与随机币无关。Alice 与 Bob 的接力模拟和 $A$ 在这条流上的完整运行具有相同的状态及输出分布。每当 $A$ 正确返回 $F_0$，Bob 就正确返回 $x_i$；失败时若 $Y$ 不在 $\{n,n+1\}$，可约定任意输出。因此对每个固定输入都有

这一步没有对 $x$ 或 $i$ 取平均，也没有让 Bob 看过随机摘要后再选择 $i$。普通固定流保证已经足够，不需要额外假设算法抵抗自适应输入。

现在调用公共币 INDEX 的单向下界，得到

确定性精确算法甚至满足 $S\ge n$，因为不同位串必须留下不同消息；若另有免费常数控制，则是 $S+O(1)\ge n$。本族中 $U=2n,m=n+1$，所以也可写作 $\mathrm{\Omega }(U)$ 或 $\mathrm{\Omega }(m)$。这只是本组参数关系下的等价写法，不表示任意独立的 $m,U$ 都能互换。

用 10110 完整复算 ​

令 $n=5,x=10110$。Alice 无论面对哪个索引，都处理同一个前缀

对应整数键 $2,3,6,8,9$。若 Bob 持有 $i=4$，他追加 $(4,1)$，即键 8。最终正频率为 $2,1,1,1,1$，故 $F_0=5$，Bob 输出 $6-5=1=x_4$。若另一次输入为 $i=2$，Bob 追加 $(2,1)$，即键 4，六键全异，$F_0=6$，输出 $6-6=0=x_2$。

随机算法在两次独立运行中未必留下相同的实际比特串，但消息分布只依赖相同的 $x$ 与前缀随机性。固定同一组前缀随机币作比较时，配置 $q_5$ 完全相同。其职责正是在尚不知道索引时，已经足以支持两个可能的续跑实例。

空间单位和两遍算法 ​

每个整数键需要 $\lceil {\log }_2(2n)\rceil$ bits，整个输入编码长度为 $\mathrm{\Theta }(n\log n)$ bits。因此本证明是相对于到达项数的线性空间下界，不能写成相对于输入总 bit 长度线性。若算法用 $W$ 个宽 $w$ 的 word，应写 $Ww=\mathrm{\Omega }(n)$；当 $w=\mathrm{\Theta }(\log n)$ 时，只得到 $W=\mathrm{\Omega }(n/\log n)$。另一方面，$U$-bit 已见键表加 $O(\log U)$-bit 计数器即可精确计数，故本族的单遍 bit 空间量级为 $\mathrm{\Theta }(n)$。

若算法扫描 $p$ 遍，通常每遍 Alice 把状态交给 Bob，相邻两遍之间 Bob 再交还 Alice，共 $2p-1$ 次传递，通信至多 $(2p-1)S$。这是交互协议。INDEX 可以让 Bob 先用 $\lceil {\log }_{2}n\rceil$ bits 告诉 Alice 索引，再由 Alice 回答一 bit，所以它的单向线性下界不能推出多遍空间 $\mathrm{\Omega }(n/p)$。

本 promise 确实有两遍 $O(\log n)$-bit 算法：第一遍用一个寄存器不断覆盖保存当前键，流末就记住了最后键 $(i,1)$；第二遍维护位置计数器，只检查前 $n$ 项是否等于这个键，用一 bit 记录是否命中。命中就输出 $F_0=n$，否则输出 $n+1$。寄存器和位置计数器各占 $O(\log n)$ bits。该算法只解决本受限流族，不能据此宣称一般精确不同元素计数也有相同的两遍空间上界。

如果索引在前缀之前就公开，算法也可从一开始只检查指定键，记住索引及一个命中位即可。这进一步说明，本归约的困难来自“先形成摘要、后到达索引”的顺序，而不是键对的写法。

同一编码能迁移到哪些频率矩 ​

对同一条流，所有频率之和总是 $F_1=n+1$，因此一阶矩不能区分两个 INDEX 答案。二阶频率矩公理库频率矩问题Frequency moments用 F_k 汇总频率向量，统一不同项数、流长与重复集中度目标。则不同：全异时为 $n+1$；重复时一个键贡献 $2^2$，其余 $n-1$ 个键各贡献 1，故

精确 $F_2$ 算法可用 $x_i=(F_2-n-1)/2$ 解码，也需要单遍 $\mathrm{\Omega }(n)$ bits。在上述算例中，$i=4$ 时 $F_2=8$，$i=2$ 时 $F_2=6$，而两者 $F_1$ 都是 6。迁移一个下界需要重新核对目标输出能否区分答案，不能仅因为记号同属频率矩就照搬。

若输出有加性误差 $\eta <1/2$，$F_0$ 的两个可能输出区间仍被阈值 $n+1/2$ 分开，因而下界保留。对 $F_2$，加性误差 $\eta <1$ 时可用阈值 $n+2$。等号处闭区间接触，原有解码不再保证正确。

相对误差必须按两个真实值分别计算。要区分 $F_0=n$ 与 $n+1$，需

同理，区分 $F_2=n+1$ 与 $n+3$ 需要 $\epsilon <1/(n+2)$。这些条件随 $n$ 增长而收紧，本构造不能排除常数相对误差的小空间算法，也不与 HyperLogLog 或 AMS 的近似保证矛盾。这里得到的是特定构造的可分间隔，不是最优的精度依赖下界。

另外两类执行切口 ​

线性 Sketch公理库线性 SketchLinear sketch以线性映射 Sf 压缩频率向量，使更新与分布式摘要可直接相加。提供另一种本地拼接方式。Alice 发送 $A{v}_x$，Bob 计算 $A(v_x+v_y)=A{v}_x+A{v}_y$ 后解码。若摘要含 $d$ 个、每个 $w$ bits 的坐标，消息长为 $dw$，不能把它称作“一个向量”就算一 bit。矩阵及种子的公开性仍须与协议一致。若保证只对每个固定向量成立，Bob 不能看完随机摘要再自适应选择 $v_y$ 并沿用原保证。本页的键对归约则不要求流算法线性或可合并：完整状态可续跑就足够。

在单元探测模型公理库单元探测模型Cell-probe model将内部计算设为免费、只统计对 w 位内存单元读写次数的数据结构复杂度模型。的静态只读查询中，Alice 可持有由 $x$ 预处理出的内存表，Bob 持有查询 $y$。若表有 $M\ge 1$ 个 cell、宽度为 $w\ge 1$，一次读取可由 Bob 发送 $\lceil {\log }_{2}M\rceil$-bit 地址，Alice 返回 $w$-bit 内容模拟。$t$ 次 probe 产生总通信至多 $t(\lceil {\log }_{2}M\rceil +w)$，且必须保留后续地址依赖此前内容的交互顺序。将所有地址预先发送只适用于非自适应查询。

一般交互模型包含单向协议，所以同一输入、错误及输出口径下，适用于所有交互协议的下界通常也约束单向协议。不能反过来，用一个仅对单向协议成立的下界约束模拟产生的多轮协议。归约最终适用什么定理，取决于实际产生的协议能力，而不是我们希望得到的空间公式。

CONGEST割模拟公理库CONGEST 割模拟与四色四环下界CONGEST cut simulation · Two-party simulation across a graph cut · CONGEST 通信下界归约构造直径至多3的四色四环检测实例，逐轮模拟固定图割，以精确消息编码把DISJ通信下界换算为CONGEST轮数下界。将执行切口换成固定图割：两方各模拟一侧，逐轮缓存后交换跨割消息，用完整变长编码保留位数。带颜色四环把k²个DISJ输入位放进4k+2顶点、2k+1条割边的直径三图族。