Corruption / rectangle bound

近单色矩形质量上界与协议好叶质量下界共同推出通信下界 — Corruption 界的好叶抽取

形式陈述

近单色矩形参数

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

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

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

M^b_\eta(f;\mu) =\max_{R=A\times B} \{g_b(R):e_b(R)\le\eta g_b(R)\},

以及 corruption bound

\operatorname{corr}^b_\eta(f;\mu) =-\log_2 M^b_\eta(f;\mu).

值大表示：任何错误相对 $b$ -质量很少的组合矩形，都只能捕获极小的 $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) \le\frac1\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}, \qquad e_b(R)\le\eta g_b(R).

按 $M^b_\eta$ 的定义， $2^{-\operatorname{corr}^b_\eta}\ge\beta2^{-c}$ ，整理得到

\boxed{ c\ge \operatorname{corr}^b_\eta(f;\mu) +\log_2\beta }.

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

条件错误口径可以直接换算：只要 $g_b(R)+e_b(R)>0$ ， $e_b(R)\le\eta g_b(R)$ 等价于 $\Pr[f\ne b\mid R]\le\eta/(1+\eta)$ 。例如允许错误与正确质量之比为 $1/4$ ，对应条件错误上限是 $1/5$ ，不是 $1/4$ 。零质量矩形可以忽略；当 $M^b_\eta=0$ 时采用 $-\log_2 0=+\infty$ 的扩展值，但实际抽取还必须满足 $\beta>0$ 。

直觉

低通信协议只有少量叶矩形。若它在分布上错误很低，正确标成颜色 $b$ 的概率质量不能全落在污染严重的叶里，因此至少有一个叶既相当大又近乎 $b$ -单色。Corruption 下界排除的正是这种叶，从而把“所有大矩形都会被另一颜色污染”转成 bit 下界。

例子与边界

Equality 的零错误实例

令整数 $N\ge1$ 、 $X=Y=[N]$ ， $f(x,y)=\mathbf1[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^1_0(f;\mu)=\frac1{N^2}, \qquad \operatorname{corr}^1_0(f;\mu)=2\log_2N.

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

c\ge2\log_2N+\log_2(1/N)=\log_2N.

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

为什么常数错误需要先放大

若 $\alpha=1/2$ 、 $\eta=1/4$ ，直接代入 $\delta=1/3$ 会得到负的 $\beta$ ，此时抽取式没有下界含义。这不表示 corruption 方法不能处理逐输入错误至多 $1/3$ 的随机协议，而是要在固定随机币之前，先用概率放大独立重复随机协议并多数表决。仅有平均错误界的确定性分布协议不能这样放大：它会在同一批输入上反复给出相同错误。例如把总错误降到 $\delta=1/20$ ，就有 $\beta=1/2-1/20-1/5=1/4$ ，从而放大后的通信 $c'$ 满足 $c'\ge\operatorname{corr}^b_{1/4}-2$ 。

由于从 $1/3$ 降到 $1/20$ 只需固定次数重复， $c'\le kc$ ，原通信满足 $c\ge(\operatorname{corr}^b_{1/4}-2)/k$ 。这保留渐近线性下界，却不是把放大后的精确常数原封不动赋给原协议。

与 discrepancy 的差异

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

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

错误口径边界

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

对随机协议，先用分布复杂度或固定随机币得到一条 $\mu$ -平均错误确定性协议，再做叶抽取。逐输入随机错误不能直接给每棵随机树的近单色叶。

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

推论与应用

该方法适合输出不对称、one-sided 或困难分布上某一颜色结构更清楚的问题，也是随机 Disjointness 下界证明的核心接口之一。使用时必须把颜色先验质量、条件或总错误、近单色参数与固定随机币步骤放在同一账本中。

参考资料

Rahul Jain and Hartmut Klauck, “The Partition Bound for Classical Communication Complexity and Query Complexity”, CCC, 2010，第 2 节；矩形界及其平滑版本的归一化。
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.

形式陈述 ​

近单色矩形参数 ​

从低错误协议抽取好叶 ​

Equality 的零错误实例 ​

为什么常数错误需要先放大 ​

与 discrepancy 的差异 ​

错误口径边界 ​