平滑 discrepancy

普通 discrepancy 要求目标符号矩阵本身在每个矩形中平衡，少量异常格可能制造抵消或毁掉一个好分布。平滑版本允许对这些格付出明确预算后重新选择附近函数，问困难是否在小扰动下仍存在。

LP 中 $w_R-v_R$ 是用正负矩形权重重建符号目标；slack 允许重建值位于 $[1,1+\eta ]$。对偶则寻找一张加权见证，使每个矩形的相关性都小。这个凸对偶与近似 ${\gamma }_2$ 的分解范数路线相接，但两者的归一化不能凭“都叫 generalized discrepancy”而混写。

对二阶 XOR，令四个 singleton 矩形为 $R_{ij}=\{i\}\times \{j\}$。在 $f(i,j)=1$ 的格取 $w_{R_{ij}}=1$，在 $f(i,j)=0$ 的格取 $v_{R_{ij}}=1$，其余变量为零。每格恰被自己的 singleton 覆盖，约束和为 $1$，故对任意 $\eta \ge 0$ 都是目标值 $4$ 的可复算 primal 可行解。

这只是上界证书，不是下界；要证明最优值为 $4$ 还需 dual witness。例子刻意说明“写出矩形覆盖”与“证明通信困难”方向相反。若允许修改一个质量 $1/4$ 的格，XOR 的附近函数和 discrepancy 会变化，所以平滑预算必须与分布同时报告。

平滑 discrepancy 仍是双侧相关性方法，不等于平滑矩形界公理库平滑矩形界Smooth rectangle bound · Smooth corruption bound以单一输出标签的分数矩形覆盖允许少量目标扰动，形成介于 smooth discrepancy 与 partition bound 之间的一侧下界。的一侧纯度条件。对 partial function，未定义格是否可当作免费修改、是否进入分布支撑，必须由所用版本说明。

LP 对偶把“对所有矩形”的普遍量词压成一个可验证加权矩阵；把该 witness 代入协议叶分解即可推出 randomized communication lower bound。Jain–Klauck 证明 smooth discrepancy 受 smooth rectangle bound 控制，后者又受 partition bound 控制，形成有严格方向的 LP 层级。

方法强度依赖 $\eta$、平滑质量、输出编码和 discrepancy 取倒数的 convention。某页若把 discrepancy 定义成小数值，本页 LP 则以其倒数作为大下界量；比较前必须先统一方向。没有大 dual 值只表示这类证书失败，不表示存在低通信协议。