Corruption / rectangle bound

近单色矩形参数 ​

设 $f:X\times Y\to \{0,1\}$、输入分布为 $\mu$，固定目标输出 $b\in \{0,1\}$。对矩形 $R$，记

$$g_b(R)=\mu (R\cap f^{-1}(b)),e_b(R)=\mu (R\cap f^{-1}(1-b)).$$

若 $e_b(R)\le \eta g_b(R)$，称 $R$ 对颜色 $b$ 是 $\eta$-近单色的。定义最大可保留的 $b$-质量

$$M_{\eta }^b(f;\mu )=\underset{R=A\times B}{max}\{g_b(R):e_b(R)\le \eta g_b(R)\},$$

以及 corruption bound

$${\mathrm{corr}}_{\eta }^b(f;\mu )=-{\log }_2{M}_{\eta }^b(f;\mu ).$$

值大表示：任何错误相对 $b$-质量很少的组合矩形公理库通信矩阵与组合矩形Communication matrix · Combinatorial rectangle将两方函数排成输入行列矩阵，并以行集和列集的笛卡尔积刻画协议能够共同隔离的区域。，都只能捕获极小的 $b$-输入概率。不同文献也可能按总矩形质量归一化或使用条件错误 $e/(e+g)$；参数转换后才能比较数值。

从低错误协议抽取好叶 ​

设确定性协议 $P$ 通信至多 $c$，在 $\mu$ 下总错误至多 $\delta$。令

$$\alpha =\mu (f^{-1}(b)).$$

考察所有输出标签为 $b$ 的叶矩形 $R_j$。它们正确覆盖的 $b$-质量总和至少 $\alpha -\delta$，因为最多 $\delta$ 质量的 $b$-输入被协议错标为 $1-b$；这些叶中来自 $1-b$ 的污染总和至多 $\delta$。

固定 $\eta >0$。把满足 $e_b(R_j)>\eta g_b(R_j)$ 的叶称为坏叶。坏叶的 $b$-质量满足

$$\sum _{j\text{ bad}}{g}_b(R_j)<\frac{1}{\eta }\sum _{j\text{ bad}}{e}_b(R_j)\le \frac{\delta }{\eta }.$$

因此好叶共同携带至少

$$\beta =\alpha -\delta -\frac{\delta }{\eta }$$

的 $b$-质量。只要 $\beta >0$，而叶数至多 $2^c$，至少有一个好叶 $R$ 满足

$$g_b(R)\ge \frac{\beta }{2^c},e_b(R)\le \eta g_b(R).$$

按 $M_{\eta }^b$ 的定义，$2^{-{\mathrm{corr}}_{\eta }^b}\ge \beta 2^{-c}$，整理得到

$$\boxed{{\displaystyle c\ge {\mathrm{corr}}_{\eta }^b(f;\mu )+{\log }_2\beta }}.$$

当 $\alpha ,\eta$ 为常数、$\delta$ 足够小使 $\beta$ 为正常数时，损失只是 $O(1)$。这条抽取链说明为什么输出先验质量不能省略：若 $b$ 本身极罕见，协议可能用很少叶覆盖它，$\log \alpha$ 会进入账本。

Equality 的零错误实例 ​

令 $X=Y=[N]$，$f(x,y)=\mathbf{1}[x=y]$，$\mu$ 均匀分布在 $N^2$ 个输入上，取 $b=1$、$\delta =\eta =0$。1-输入总质量为 $\alpha =1/N$。

任何零污染的 1-矩形至多含一个对角点。若含 $(x,x)$ 与 $(y,y)$ 且 $x\ne y$，交叉输入 $(x,y)$ 也在矩形中却输出 $0$。所以

$$M_0^1(f;\mu )=\frac{1}{N^2},{\mathrm{corr}}_0^1(f;\mu )=2{\log }_{2}N.$$

零错误时无需使用含 $\delta /\eta$ 的坏叶筛除：全部 1-叶本来就是零污染，直接取可覆盖质量 $\beta =\alpha =1/N$。于是

$$c\ge 2{\log }_{2}N+{\log }_2(1/N)={\log }_{2}N.$$

若只看到 $2\log N$ 的 rectangle 参数便直接声称通信下界同样大，就漏掉了 1-输入先验质量 $1/N$；完整证明链恰好抵消其中一半。

与 discrepancy 的差异 ​

Discrepancy 衡量每个矩形中正负质量的 绝对差，允许两侧相互抵消；corruption 直接问一个质量大的矩形能否把错误相对于目标颜色压到很低。后者天然不对称，要固定 $b$，特别适合 one-sided 或对某一输出更精细的分布论证。

小 discrepancy 常能立即给双侧随机下界，但可能被少量偏置质量控制；corruption 可以忽略一定污染并追踪大矩形。两者都使用矩形，却不是换个名字的同一个参数。

错误口径边界 ​

若协议只保证 $b$-输入上的条件错误 ${\delta }_b$ 与 $(1-b)$-输入上的条件错误 ${\delta }_{1-b}$，抽取式应分别把它们乘相应先验质量，而不是用一个总 $\delta$。单侧错误可以让某个污染项恰为零，得到更强参数；双侧版本不能冒用该简化。

对随机协议，先用分布复杂度公理库分布通信复杂度Distributional communication complexity固定输入分布后，以确定性协议在该分布下的平均错误衡量通信，是随机最坏复杂度的分布侧接口。或固定随机币得到一条 $\mu$-平均错误确定性协议，再做叶抽取。逐输入随机错误不能直接给每棵随机树的近单色叶。

最后，证明 $M_{\eta }^b$ 小必须覆盖 所有 组合矩形。只分析由某个自然协议产生的矩形族，无法排除另一条协议选择完全不同的行列子集。

参考资料

• Alexander A. Razborov, “On the Distributional Complexity of Disjointness,” Theoretical Computer Science 106(2), 1992, pp. 385–390.
• Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao, “How to Compress Interactive Communication,” STOC, 2010, rectangle-bound background.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 4.