Fooling set 通信下界

Fooling set 条件 ​

设 $f:X\times Y\to \{0,1\}$，固定 $b\in \{0,1\}$。集合

$$F=\{(x_1,y_1),\dots ,(x_m,y_m)\}\subseteq f^{-1}(b)$$

称为 $b$-fooling set，若对任意 $i\ne j$，至少一个交叉输入满足

$$f(x_i,y_j)\ne b\text{或}f(x_j,y_i)\ne b.$$

所有关键点自身都为 $b$，但任取两个，把 Alice 部分与 Bob 部分交叉后，至少有一个格子跳出颜色 $b$。名称中的 “fooling” 表示：若协议试图让两个关键点共享同一 $b$-叶，组合矩形的闭合性会把那个异色交叉点也拖进来。

单矩形引理 ​

引理。 任意 $b$-单色组合矩形至多包含 $F$ 中一个点。

证明。 反设矩形 $R=A\times B$ 同时包含 $(x_i,y_i)$ 与 $(x_j,y_j)$，其中 $i\ne j$。由笛卡尔积闭合，$x_i,x_j\in A$ 且 $y_i,y_j\in B$，所以

$$(x_i,y_j),(x_j,y_i)\in A\times B=R.$$

$R$ 是 $b$-单色矩形，两个交叉输入的函数值都应为 $b$；这与 fooling set 条件“至少一个不为 $b$”矛盾。故引理成立。$◻$

注意条件只要求两个交叉格中至少一个异色，并不要求二者都异色。把它加强为“两者都反色”会无谓缩小可构造的集合，也不是证明所需。

通信下界定理 ​

定理。 若 $f$ 有大小为 $m$ 的 fooling set，则

$$D^{\mathrm{cc}}(f)\ge \lceil {\log }_{2}m\rceil .$$

证明。 设有最坏通信 $c$ 的确定性零误差协议。每个协议叶对应一个单色组合矩形公理库通信矩阵与组合矩形Communication matrix · Combinatorial rectangle将两方函数排成输入行列矩阵，并以行集和列集的笛卡尔积刻画协议能够共同隔离的区域。。所有 $F$ 中的点函数值均为 $b$，因此它们只能落到 $b$-叶；由单矩形引理，每个这样的叶至多容纳一个关键点，协议至少有 $m$ 个可达叶。

深度至多 $c$ 的二叉协议树最多有 $2^c$ 个叶，所以 $m\le 2^c$，即 $c\ge \lceil {\log }_{2}m\rceil$。对所有正确协议取最小值得到结论。$◻$

证明也直接说明任何 $b$-单色矩形 cover 至少需要 $m$ 块，因为每块至多覆盖一个关键点。这个 cover 结论可用于证书式通信；确定性结论还利用协议叶覆盖整张矩阵并形成树。

Equality 的对角构造 ​

令 $X=Y=\{0,1{\}}^n$，${\mathrm{EQ}}_n(x,y)=1$ 当且仅当 $x=y$。取全部对角输入

$$F=\{(z,z):z\in \{0,1{\}}^n\}.$$

每个点的函数值为 $1$。对不同 $z,z^{\prime }$，交叉输入 $(z,z^{\prime })$ 与 $(z^{\prime },z)$ 都不相等，函数值均为 $0$，所以 $F$ 是大小 $2^n$ 的 $1$-fooling set。定理给出

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

若只约定 Bob 输出，Alice 发送完整 $x$ 后 Bob 与 $y$ 比较，使用 $n$ bit；若要求输出成为公开叶标签，Bob 再发送结果，共 $n+1$ bit。下界与 convention 因而至多差最后一 bit。这里关键不是矩阵共有 $2^n$ 个对角格，而是任何两个对角格都不能被同一个 $1$-矩形合并；单纯数很多个 $1$ 并不足以证明它们需要很多叶。

怎样构造而不自欺 ​

候选集合首先必须全在同一颜色中。随后要检查每一对不同关键点，而不是只检查相邻点或某个代表。若存在一对使两个交叉值仍为 $b$，那两个点可能共处一个 $b$-矩形，集合就不满足定义。

对关系问题或多值函数，需先固定叶输出 $z$，再要求关键点都允许或需要该输出，并让交叉输入中至少一个不允许 $z$。把不同合法输出的点混在同一 fooling set，会失去“同叶必须同标签”的矛盾链。

方法边界 ​

Fooling set 给出的是一种可展示的组合障碍，不保证对每个函数都紧。某些矩阵需要许多矩形，却不存在同等规模的两两 fooling set；两两交叉条件过强，可能抓不到更高阶的覆盖困难。

反过来，一个大的 fooling set 同时约束确定性叶与同色 cover，因而证明简洁、量词透明。若构造只能得到很小集合，不能据此断言问题容易；它只说明这项证据没有给出更强下界。

允许错误的随机协议还可能把少量关键点答错，单色叶论证不再逐点成立。把确定性 fooling-set 证明原样冠以“高概率”不会得到随机下界；必须额外控制错误分布或改用适合近单色矩形的工具。

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Section 1.3.
• Dietzfelbinger, Hromkovič, and Schnitger, “A Comparison of Two Lower-Bound Methods for Communication Complexity,” Theoretical Computer Science 168(1), 1996, pp. 39–51.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 2.