Indexing 通信问题

问题定义 ​

Alice 持有字公理库字Word · String从某个有限位置集到字母表的函数，即有限符号序列。 $x=x_1\cdots x_n\in \{0,1{\}}^n$，Bob 持有索引 $i\in [n]$。在 Alice-to-Bob 的单向模型中，目标计算

$${\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$ 的固定消息只有 $2^c$ 种，故 $2^c\ge 2^n$，即 $c\ge n$。于是

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

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

一次具体执行 ​

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

这两次执行共享消息、改变解码问题，正好体现单向摘要的职责。Alice 不能只发送“当前被问 bit”，因为发送时尚不知道 $i$；也不能让消息依赖 Bob 尚未公开的索引。

常数错误随机下界的状态 ​

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

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

下面给出一个不依赖后续一般方法的计数证明轮廓。令 $x$ 与 $i$ 独立均匀。最坏输入错误至多 $1/3$ 蕴含该分布下平均错误也至多 $1/3$。再对公共随机币平均，可固定一条随机带，使所得确定性 $c$-bit 协议的平均坐标错误至多 $1/3$。

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

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

协议至多产生 $2^c$ 个这样的串。平均坐标错误就是 $d_H(x,z(m(x)))/n$ 的平均值。由 Markov 不等式，至少 $1/5$ 的 $x$ 满足

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

否则平均距离会超过 $n/3$。半径 $5n/12$ 的 Hamming 球大小至多 $2^{H_2(5/12)n}$，其中 $H_2(p)=-p{\log }_{2}p-(1-p){\log }_2(1-p)<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)$。常数并非重点；关键是 bounded-error 消息仍须让 Bob 同时重构绝大多数可能坐标，而不能只对一个固定 $i$ 有效。

流式空间下界接口 ​

若一趟 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将受限算法的执行切成双方可本地模拟的片段，把跨切口状态或访存内容变成消息并保留全部参数。会把这些参数逐项列成检查表；Indexing 提供困难母问题，本页不把“可归约”当作无需构造的口号。

模型边界 ​

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

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

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

参考资料

• 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, Lectures 2 and 4.
• 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.