平滑 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 可行解。

这首先只是上界证书。对这个小例子，还能显式写出匹配的对偶：四格各取 ${\mu }_{ij}=1$，并令 ${\varphi }_{ij}=0$。XOR 的符号棋盘在整个矩阵、任意完整行或列上的和都是零，在 singleton 上为 $\pm 1$；这些已经列尽二阶矩阵的非空矩形。因此所有矩形约束均满足，而对偶目标为 $4$，证明 ${\mathrm{sdisc}}_{\eta }({\mathrm{XOR}}_1)=4$ 对每个 $\eta \ge 0$ 都成立。

这展示了两种证书的相反方向：primal 构造证明“至多这么贵”，dual 构造证明“不能更便宜”。自然定义若允许改变一个均匀质量为 $1/4$ 的格，必须取平滑半径 $\delta >1/4$，因为该版本的距离约束是严格小于；不能把 LP 的 $\eta$ 直接当成可以翻转的格子比例。

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

LP 对偶把“对所有矩形”的普遍量词压成一个可验证加权矩阵。为看清错误参数，设公共币协议错误至多 $\epsilon <1/2$，通信至多 $c$。对每棵树给输出 $1$ 的叶记正号，输出 $0$ 的叶记负号，再按随机币取平均，所得矩形线性组合 $h$ 满足 $1-2\epsilon \le (2f-1)h\le 1$。把全部矩形权重除以 $1-2\epsilon$，便得到 $\eta =2\epsilon /(1-2\epsilon )$ 时的 primal 可行解，总权重至多 $2^c/(1-2\epsilon )$。

所以任何该参数下目标为 $L$ 的 dual witness 都给出 $c\ge {\log }_{2}L+{\log }_2(1-2\epsilon )$。LP 的允许幅度 $\eta$ 和协议错误 $\epsilon$ 通过这一缩放相连，不能直接把二者写成相同数字。Jain–Klauck 证明 smooth discrepancy 受 smooth rectangle bound 控制，后者又受 partition bound 控制，形成有严格方向的 LP 层级。

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