Equality 通信问题

问题与输出 convention ​

Alice 持有 $x\in \{0,1{\}}^n$，Bob 持有 $y\in \{0,1{\}}^n$，目标计算

$${\mathrm{EQ}}_n(x,y)=\mathbf{1}[x=y].$$

本页比较两种常见输出口径。单向模型只要求 Bob 输出；一般确定性协议采用公开叶标签，使双方从 transcript 都知道答案。前者可以省掉 Bob 回传结果的一 bit。若不先写明这一区别，“确定性是 $n$ 还是 $n+1$”会成为 convention 争论而非数学分歧。

确定性上界 ​

在 Alice-to-Bob 的单向模型公理库单向通信复杂度One-way communication complexity限制 Alice 只向 Bob 发送一次消息，由 Bob 结合自身输入输出，并按消息 bit 数衡量代价。中，Alice 发送完整 $x$，Bob 逐位与 $y$ 比较并输出，使用 $n$ bit。若输出必须公开，Bob 再发送比较结果，总代价 $n+1$ bit。

这条协议允许双方做任意本地计算，却没有压缩 Alice 的串。原因不在比较过程昂贵，而在 Bob 的 $y$ 可能是 $2^n$ 个串中的任意一个；Alice 在发送时不知道 Bob 将用哪一行等价性测试解释消息。

确定性下界与精确值 ​

Equality 矩阵的每个对角输入 $(z,z)$ 都输出 $1$。两个不同对角点不能落入同一个 1-单色矩形：若 $(z,z)$ 与 $(z^{\prime },z^{\prime })$ 同处其中，交叉点 $(z,z^{\prime })$ 也被矩形包含，却输出 $0$。因此公开叶协议至少需要 $2^n$ 个不同的 1-叶。

函数还有 0-输入，协议至少再需要一个 0-叶，所以可达叶总数至少 $2^n+1$。深度 $c$ 的二叉树最多有 $2^c$ 个叶；若 $c\le n$，最多只有 $2^n$ 个叶，不足以同时容纳这些输入。故公开输出 convention 下

$$D^{\mathrm{cc}}({\mathrm{EQ}}_n)\ge n+1.$$

与上界合并得到精确值 $n+1$。在 Bob-only 单向模型中，只看不同 Alice 输入诱导的函数行：任意 $x\ne x^{\prime }$ 在 Bob 输入 $y=x$ 上给出不同答案，所以 $2^n$ 个串必须产生不同消息，至少需要 $n$ bit；完整传输上界同样紧。

公共随机内积指纹 ​

现在允许双方免费看到与输入独立的公共随机串。利用它们独立均匀选择 $k$ 个向量

$$r^{(1)},\dots ,r^{(k)}\in \{0,1{\}}^n.$$

Alice 发送 $k$ 个 parity 指纹

$$a_j=⟨r^{(j)},x⟩mod2.$$

Bob 本地计算 $b_j=⟨r^{(j)},y⟩mod2$。若所有 $a_j=b_j$ 就输出相等，否则输出不等；公开输出时再把这一判定回传一 bit。

当 $x=y$ 时，每个内积必然相同，协议从不误拒。若 $x\ne y$，令 $d=x\oplus y\ne 0$。选择一个 $d_i=1$ 的坐标；在固定其余随机 bit 后，$⟨r,d⟩$ 随 $r_i$ 翻转，故均匀取 $0,1$，一次碰撞概率恰为 $1/2$。$k$ 次独立选择全部碰撞的概率为 $2^{-k}$。

因此 Bob-only 公共币协议以 $k$ bit 通信达到单侧错误 $2^{-k}$；公开输出使用 $k+1$ bit。取 $k=\lceil {\log }_2(1/\epsilon )\rceil$，通信只依赖目标误差，不随 $n$ 增长，而确定性需要线性 bit。这是随机化价值的最小、可完整追踪的例子。

随机种子不是输入消息 ​

公共随机向量无需发送，因为模型假设双方在看到输入前已经共享同一随机串。它们不携带 $x$ 或 $y$；真正跨边界的是 Alice 的 $k$ 个指纹 bit。若系统没有共享随机性，Alice 私下选 $r^{(j)}$ 后就必须把足以重建这些向量的种子也发给 Bob，通信账目会改变。

把某个固定哈希函数写死也不能保留上述逐输入保证。对任何压缩到少于 $n$ bit 的确定性指纹，都有不同 $x,y$ 发生碰撞；对手可选择这对输入，使协议必错。随机协议的量词是对每个固定不同输入，碰撞只占随机选择的一小部分。

失败边界 ​

内积分析依赖 $r$ 在整个 Boolean cube 上均匀，或至少对每个非零 $d$ 保证 parity 无偏。用几个固定坐标抽样不能测试普通 Equality：两个串可能只差一个未抽中的位置，常数次采样几乎总会误收。

$k$ 次放大还需要独立或足以控制联合碰撞的指纹。重复发送同一个 parity $k$ 次，通信变成 $k$ bit，错误仍是 $1/2$；消息重复不会制造随机独立性。

协议只回答是否相等，不找出第一个差异坐标，也不估计 Hamming 距离。后两项输出携带更多结构，需要另行定义通信任务和保证。

参考资料

• Andrew Chi-Chih Yao, “Some Complexity Questions Related to Distributive Computing,” STOC, 1979, pp. 209–213.
• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapters 1 and 3.
• Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015, Lecture 2.