Indexing 通信问题 | Codeboy's Blog

形式陈述

问题定义

Alice 持有字 $x=x_1\cdots x_n\in\{0,1\}^n$ ，Bob 持有索引 $i\in[n]$ 。在 Alice-to-Bob 的单向模型中，目标计算

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

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

确定性复杂度恰为 n

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

因此 $2^n$ 个 Alice 输入必须产生 $2^n$ 条不同消息。长度至多 $c$ 的固定消息只有 $2^c$ 种，故 $2^c\ge2^n$ ，即 $c\ge n$ 。于是

D^\rightarrow(\operatorname{INDEX}_n)=n.

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

常数错误随机下界

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

R^\rightarrow_{1/3}(\operatorname{INDEX}_n)=\Omega(n).

令 $x$ 与 $i$ 独立均匀。最坏输入错误至多 $1/3$ 蕴含该分布下平均错误也至多 $1/3$ 。再对公共随机币平均，可固定一条随机带，使所得确定性 $c$ -bit 协议的平均坐标错误至多 $1/3$ 。

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

z(m)=(g(m,1),\ldots,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_2p-(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=\Omega(n)$ 。常数并非重点；关键是 bounded-error 消息仍须让 Bob 同时重构绝大多数可能坐标，而不能只对一个固定 $i$ 有效。

直觉

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$ 。

这两次执行共享消息、改变解码问题，正好体现单向摘要的职责。Alice 不能只发送“当前被问 bit”，因为发送时尚不知道 $i$ ；也不能让消息依赖 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=\Omega(n)$ 。

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

通信下界归约范式会把这些参数逐项列成检查表；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, 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.

形式陈述 ​

问题定义 ​

确定性复杂度恰为 n ​

常数错误随机下界 ​

一次具体执行 ​

模型边界 ​

流式空间下界接口 ​