平滑矩形界

传统 corruption 问是否存在一块大而近乎 $z$-单色的矩形。平滑矩形界允许先修正一小部分输入，再问附近函数是否仍排斥这种矩形；LP 则把“很多协议树中的候选矩形”连续化为权重。

具体说，对一条通信至多 $c$ 的公共币协议，令 $w_R$ 等于输出 $z$ 的叶矩形 $R$ 在随机协议树中出现的期望次数。对每棵固定树，每个输入只落在一个叶内，所以 $\sum _{R\ni (x,y)}{w}_R$ 恰是协议输出 $z$ 的概率。在目标格上它至少为 $1-\epsilon$，在其他定义格上至多为 $\epsilon$，且不会超过 $1$。

每棵树至多有 $2^c$ 个叶，因此这组权重满足 $\sum _R{w}_R\le 2^c$。于是 ${\mathrm{srec}}_{\epsilon }(f)\le 2^c$，也就是 $c\ge {\log }_2{\mathrm{srec}}_{\epsilon }(f)$。这是 LP 数值到通信 bit 数的必要对数转换；找到便宜的可行覆盖只给 LP 上界，证明通信下界需要证明所有可行覆盖都昂贵。

与双侧 discrepancy 的正负抵消不同，本页只追踪一个标签的覆盖和污染。因此它能识别某一类输入难以被近单色矩形捕获的情形，即使整体符号和因另一侧结构而有较大 discrepancy。

对零误差二阶 XOR，固定 $z=1$。这里 ${\mathrm{XOR}}_1(x,y)=x\oplus y$，两个 $1$-格是 $(0,1)$ 和 $(1,0)$，位于反对角位置；任何同时包含二者的组合矩形也包含两个 $0$-格，因 $\epsilon =0$ 不合法。两个 singleton 各赋权 $1$ 给出目标值 $2$ 的可行解。

反之，每个合法正权矩形至多覆盖一个 $1$-格，而每个 $1$-格的总覆盖至少 $1$，所以目标至少 $2$。因此

这与 partition LP 的值 $4$ 不冲突：后者同时给两个输出标签完整覆盖所有格，本页只保护一个输出。

在 $\epsilon =1/2$ 时，给整个矩阵矩形赋权 $1/2$ 已满足任意布尔函数的约束：目标格覆盖为 $1/2$，其他格的污染也为 $1/2$。因此该参数不再能区分复杂函数；有意义的有界错误下界必须让错误严格小于 $1/2$。若 $\epsilon \ge 1$，零权重就可行，参数完全退化。若把 $\ast$ 格当成错误输出强制低覆盖，会得到 total completion 的另一个问题。若分布不写，所谓“只改少量格”没有质量尺度。

平滑矩形界可由带 joker 的 corruption 界公理库带 joker 的 corruption 界Corruption with jokers · Joker corruption bound引入不计输出正确性的 joker 分布，以带负权的全矩形不等式排除大量近单色叶联合覆盖目标输入。构造对偶证书：joker 质量以负号抵消少量坏区域，而对所有矩形成立的不等式阻止协议用许多近单色叶覆盖目标输入。它也支配平滑 discrepancy公理库平滑 discrepancySmooth discrepancy · Smoothed generalized discrepancy允许目标函数在小概率质量上平滑改变，再以 discrepancy 的 LP 对偶证书给出更稳健的通信下界。，并被 partition bound 支配。

层级只比较下界数值，不表示方法普遍给紧结果。one-sided LP 会忘掉消息顺序、round 与信息泄露；这也解释了它为何与Set Disjointness 的信息复杂度证明公理库Set Disjointness 的信息复杂度Information complexity of Set Disjointness · Information-statistics lower bound for DISJ以单坐标 AND 的条件信息和 transcript Hellinger 距离证明 Set Disjointness 的线性信息下界。形成方法对照，后者直接追踪 transcript 泄露与 Hellinger 距离。自然定义到 LP 定义的 $\epsilon ,\delta$ 转换也必须保留；若某证明只检验一族几何矩形而非全部组合矩形，不能作为本页可行 dual 证书。