Fooling set 通信下界

协议叶的几何形状不是任意点集，而必须是 $A\times B$。这意味着它一旦同时收下两个关键点，就不能拒绝把 Alice 的一半与 Bob 的一半交叉组合。Fooling set 专门挑选一批同色点，使这种“矩形闭合”对每一对点都会制造至少一个异色格；于是关键点看似颜色相同，却无法被同一叶打包。

下界中的对数来自协议树，而不是 fooling set 定义本身。组合论先迫使至少出现 $m$ 个不同叶，信息论计数再把叶数换成深度 $\lceil {\log }_{2}m\rceil$。把这两步分开看，可以清楚辨认一个证明究竟卡在构造大集合，还是卡在把几何障碍转换为模型复杂度。

Equality 的对角构造 ​

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

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

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

构造时的成对检查 ​

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

对多值函数，可固定输出 $z$，选择函数值都为 $z$ 的关键点，并要求每对关键点至少有一个交叉输入的函数值不同于 $z$。关系问题允许一个输入有多个合法输出，因而需要更强的成对条件：对两个关键点共同允许的每个输出 $z$，至少一个交叉输入不允许 $z$。这样，无论同一叶选择哪个合法标签，都无法覆盖这一对关键点及其交叉输入。若所有关键点都只允许同一个输出 $z$，条件就退化为通常的单色 fooling set 条件。

方法边界 ​

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

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

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

单矩形引理还说明，任何 $b$-单色矩形 cover 都至少需要 $m$ 块，因为每块至多覆盖一个关键点。这个结论可直接用于证书式通信；确定性通信复杂度理路确定性通信复杂度Deterministic communication complexity在零误差确定性协议中，对所有输入的最坏通信位数取最优所得的复杂度度量。下界则进一步利用协议叶覆盖整张矩阵并组织成一棵二叉树。

Fooling set 适合能写出清晰“对角族”或互斥证书族的问题：每对关键点都给出一个可直接核验的矩形冲突。