Indexing 通信问题

形式陈述 ​

问题定义 ​

固定整数 $n\ge 1$。Alice 持有字公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。 $x=x_1\cdots x_n\in \{0,1{\}}^n$，Bob 持有索引 $i\in [n]$。在 Alice-to-Bob 的单向模型公理库单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。中，目标计算

$${\mathrm{INDEX}}_n(x,i)=x_i.$$

Alice 必须在不知道 $i$ 的情况下先发送一条消息；Bob 收到后结合索引输出一个 bit。复杂度按消息 bit 数计，索引本身属于 Bob 的私有输入，不另计通信。若允许 Bob 先发送 $i$，问题会变成两轮协议并显著容易，所以方向是定义的一部分。

确定性复杂度恰为 n ​

发送完整 $x$ 给出 $D^{\to }({\mathrm{INDEX}}_n)\le n$。为证下界，设两个不同串 $x\ne x^{\prime }$ 产生相同消息。它们至少在某个坐标 $i$ 不同；Bob 取这个 $i$ 时，看到相同消息和相同索引，却分别应输出 $x_i$ 与 $x_i^{\prime }$，不可能同时正确。

因此 $2^n$ 个 Alice 输入必须产生 $2^n$ 条不同消息。采用固定 $c$-bit 消息编码，未用位置补零，消息只有 $2^c$ 种，故 $2^c\ge 2^n$，即 $c\ge n$。于是

$$D^{\to }({\mathrm{INDEX}}_n)=n.$$

输出只有一个 bit，却需要一条能回答 任意未来索引 的消息。下界不是按输出大小计数，而是证明 Alice 的不同函数行不能碰撞。

常数错误随机下界 ​

即使允许公共随机币和每个输入至多 $1/3$ 错误，单向复杂度仍为

$$R_{1/3}^{\to }({\mathrm{INDEX}}_n)=\mathrm{\Omega }(n).$$

令 $x$ 与 $i$ 独立均匀。最坏输入错误至多 $1/3$ 蕴含该分布下平均错误也至多 $1/3$。再对公共随机币平均，可固定一条随机带，使所得确定性 $c$-bit 协议的平均坐标错误至多 $1/3$。这里通信 $c$ 是对输入和随机币的硬上限；固定币后保留的只是均匀输入分布上的平均保证，不是找到一条对所有输入都正确的随机带。私有币协议可用公共随机带的独立部分模拟公理库公共币与私有币协议Public-coin protocol · Private-coin protocol · Shared randomness in communication区分双方预先共享的输入无关随机串与各自隐藏的随机币，并说明有限输入上的 Newman 随机性压缩。，因此公共币下界同时约束私有币协议。

对每条消息 $m$，把 Bob 对所有索引的回答排成重构串

$$z(m)=(g(m,1),\dots ,g(m,n)).$$

协议至多产生 $2^c$ 个这样的串。平均坐标错误就是Hamming 距离公理库Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。 $d_H(x,z(m(x)))/n$ 的平均值。由Markov 不等式公理库Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。，距离超过 $5n/12$ 的概率至多 $(n/3)/(5n/12)=4/5$，所以至少 $1/5$ 的 $x$ 满足

$$d_H(x,z(m(x)))\le \frac{5n}{12},$$

这些良好输入落在至多 $2^c$ 个重构中心附近。计算每个中心的 Hamming 球能容纳多少输入，就能得到覆盖所需的中心数。

令 $p=5/12$。半径 $\lfloor pn\rfloor$ 的球含有

$$V(n,p)=\sum _{k=0}^{\lfloor pn\rfloor }(\genfrac{}{}{0ex}{}{n}{k})$$

个串，因为距离恰为 $k$ 的串由翻转的 $k$ 个位置唯一决定。定义二元熵 $H_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)$。当 $k\le pn$ 时，由 $p/(1-p)<1$ 可知

$$p^k(1-p{)}^{n-k}\ge p^{pn}(1-p{)}^{(1-p)n}=2^{-n{H}_2(p)}.$$

将这个下界放入二项式展开，得到

$$1=(p+(1-p){)}^n\ge \sum _{k=0}^{\lfloor pn\rfloor }(\genfrac{}{}{0ex}{}{n}{k})p^k(1-p{)}^{n-k}\ge 2^{-n{H}_2(p)}V(n,p).$$

所以 $V(n,p)\le 2^{n{H}_2(p)}$。此外，$H_2^{\prime }(p)={\log }_2((1-p)/p)>0$ 在 $0<p<1/2$ 成立，而 $H_2(1/2)=1$，故 $H_2(5/12)<1$，线性系数确实为正。$2^c$ 个重构中心要覆盖至少 $2^n/5$ 个良好输入，即使球互相重叠，覆盖数也不超过球体积之和，因此

$$2^c{2}^{H_2(5/12)n}\ge \frac{2^n}{5},$$

从而 $c\ge (1-H_2(5/12))n-{\log }_{2}5=\mathrm{\Omega }(n)$。其中 $1-H_2(5/12)\approx 0.02013$。小 $n$ 时右端可能为负，不影响渐近线性下界。证明不要求每个重构串都接近其所有原像；只需有固定比例的输入在平均坐标意义下得到足够好的重构。

对任意固定错误率 $\delta <1/2$，可取常数 $\delta <p<1/2$，同理得到 $c\ge [1-H_2(p)]n+{\log }_2(1-\delta /p)$。若允许 $\delta$ 随 $n$ 趋近 $1/2$，这两个常数就可能退化，不能再无条件写同一个线性下界。

直觉

Indexing 的输出虽然只有一个 bit，Alice 的消息却必须预先支持 $n$ 种不同解码。可以把它看成一份数据与一把稍后才出现的钥匙：若摘要丢掉了任一坐标的区别，Bob 恰好拿到对应索引时就无法补救。确定性下界用消息碰撞表达这个事实，随机下界则说明常数错误也不足以把绝大多数数据串压进少数 Hamming 球。

单向性是困难的核心。Alice 发送时不知道 Bob 会问哪一位；一旦允许 Bob 先把 $i$ 发来，Alice 只需返回 $x_i$。因此把 Indexing 嵌入另一个问题时，必须让数据部分先形成状态，查询部分随后到达，才能继承这条线性下界。

例子与边界

一次具体执行 ​

令 $x=10110$，Bob 的索引为 $i=4$。完整传输协议发送 transcript 10110，Bob 读取第四位并输出 $1$。如果 Bob 的索引改成 $2$，Alice 的消息仍必须是同一条 10110，Bob 改为读取第二位并输出 $0$。

这两次执行共享消息、改变解码问题：同一份摘要必须支持 Bob 随后提出的任意索引查询。

模型边界 ​

若 promise 限制 $x$ 只来自一个小码本，Alice 可以发送码字编号，复杂度按码本对数而不是 $n$ 计。若 Bob 的索引来自已知小集合，消息也只需保留那些坐标。线性下界针对没有这些 promise 的完整 Boolean cube 与任意索引。

允许量子消息、多个 Bob、批量索引或近似恢复比例都会产生不同问题。尤其是 Bob 只需在随机索引上平均正确，与对每个固定 $(x,i)$ bounded error 不同；计数证明先使用最坏错误推出均匀平均，反向不能成立。

Indexing 也不是数组读取的 RAM 时间复杂度。Alice 和 Bob 的本地寻址都免费，难点只在数据与索引分处两端时，单条前向消息必须保存多少信息。

推论与应用

流式空间下界接口 ​

若一趟 streaming 算法用 $S$ bit 状态解决某个可编码 Indexing 的任务，把流前缀交给 Alice、后缀交给 Bob：Alice 运行前缀后发送状态，Bob 继续并解码 $x_i$。这会得到 $S$-bit 单向协议，因此上述下界迫使 $S=\mathrm{\Omega }(n)$。

归约必须让 Alice 的前缀只依赖 $x$，Bob 的后缀只依赖 $i$，且保持原算法错误概率。若 Bob 需要查看 Alice 未发送的随机种子、算法有多趟扫描，或状态之外还能访问前缀日志，所得通信协议就不是标准 Indexing 单向协议。

通信下界归约范式公理库通信下界归约范式Communication lower-bound reduction pattern · Communication reduction for lower bounds用固定长度的 INDEX 编码，把单遍精确不同元素计数的完整内存状态变成一次消息，并逐项保留错误、随机性和空间单位。给出一个完整实例：前缀依次插入 $(j,x_j)$，后缀仅插入 $(i,1)$。宇宙大小为 $2n$，长度固定为 $n+1$，不同元素数恰为 $n+1-x_i$。因此精确不同元素计数，甚至判断这条流是否出现重复，都需要单遍 $\mathrm{\Omega }(n)$ bits。

带边信息的索引编码公理库带边信息的索引编码Index coding with side information利用接收者各自已有的消息，把一次公共广播设计成能同时补齐多个不同信息缺口的索引码。在接收者已有部分消息时重新设计公共广播，属于不同的通信任务。例如三人分别知道下一人的 bit，广播两个 XOR 即可让所有人恢复自己的 bit。它不违反标准 Indexing 的下界，因为接收者的信息条件已经改变；使用下界前须先对齐这些条件。

参考资料

• Ilan Kremer, Noam Nisan, and Dana Ron, “On Randomized One-Round Communication Complexity,” Computational Complexity 8, 1999, pp. 21–49。
• Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015，§2.4、Theorem 2.4（印刷 pp. 24–27）：公共币 INDEX 下界及 Hamming 重构证明；§2.5–2.6.1：流式应用。本文补全球体积的二项式推导。
• David P. Woodruff, “Sketching as a Tool for Numerical Linear Algebra,” Foundations and Trends in Theoretical Computer Science 10(1–2), 2014, communication lower-bound preliminaries.