带 joker 的 corruption 界

普通 corruption 要求每块大矩形中的目标 $1$ 质量都伴随足够 $0$ 污染；某些问题存在大而近单色的异常矩形，单块论证因此失败。joker 方法容许这种块存在，但证明它若含很多 $1$，就必须含更多可被统一计账的 joker 质量。

协议的 $1$-叶彼此不交。把每块不等式相加时，joker 总质量最多为一，不能被每片叶重复使用；异常矩形因此无法共同覆盖几乎所有 $1$ 输入。这是“单块可以好、全集不能都好”的全局预算。

取精确支撑 $\eta =0$，并设 ${\alpha }_0=1,{\alpha }_1=2,{\alpha }_{+}=1$。假设对所有矩形有

成本 $c$ 的确定性协议至多有 $2^c$ 个互不相交 $1$-叶，其并记为 $S_1$。逐叶求和并用 ${\mu }_{+}(S_1)\le 1$ 得

若两类条件错误都至多 $1/10$，则 ${\mu }_1(S_1)\ge 9/10$、${\mu }_0(S_1)\le 1/10$，所以 $0.7\le 2^{c-m}$，即 $c\ge m+{\log }_{2}0.7$。这条可复算轨迹展示负 joker 项为何只付一次。

必要边界是 ${\alpha }_1>{\alpha }_{+}$；否则即使错误为零，移项后也没有正余量。加性项必须是 $2^{-m}$ 这样的显式尺度，因为叶数会把它放大为 $2^{c-m}$。只对“规则矩形”检验不等式不能覆盖任意协议叶。

Chakrabarti–Regev 用此框架证明 Gap-Hamming 的线性 randomized communication lower bound；其主要技术工作是为三种精心选择的分布证明全矩形不等式，而不是上述叶求和代数。该证书可嵌入平滑矩形界公理库平滑矩形界Smooth rectangle bound · Smooth corruption bound以单一输出标签的分数矩形覆盖允许少量目标扰动，形成介于 smooth discrepancy 与 partition bound 之间的一侧下界。的对偶，因此是一种更易手算的 sufficient condition。

它不普遍支配普通 corruption：选错 ${\mu }_{+}$ 或系数可能让负项毫无帮助。joker 也不是“可随意回答的 promise 区域”的同义词；困难分布、函数未定义区和负权辅助分布是三件不同的数据，应用时都要分别报告。