平滑矩形界 | Codeboy's Blog

平滑后的单一目标输出由分数矩形近乎完整覆盖，其他定义输出只允许小污染 — 平滑矩形界的单侧分数覆盖

图中只画出部分候选矩形；可行权重仍须在每个适用的定义格满足所列覆盖与污染约束，图形本身不构成可行解见证。

形式陈述

作为corruption/rectangle 界的平滑版本，取有限非空集合 $X,Y,Z$ 和 partial function $f:X\times Y\to Z\cup\{*\}$ ，其非空定义域为 $D$ 。固定输出 $z$ 与 $\varepsilon\ge0$ ，用线性规划定义 $\operatorname{srec}^z_\varepsilon(f)$ 为 LP

\min\sum_{R\in\mathcal R}w_R

的最优值，其中 $w_R\ge0$ ，并满足

1-\varepsilon\le\sum_{R\ni(x,y)}w_R\le1 \quad ((x,y)\in f^{-1}(z)),

\sum_{R\ni(x,y)}w_R\le\varepsilon \quad ((x,y)\in\operatorname{dom}f\setminus f^{-1}(z)).

再令 $\operatorname{srec}_\varepsilon(f)=\max_{z\in Z}\operatorname{srec}^z_\varepsilon(f)$ 。它是“一侧”松弛：只强制某个输出的格被大量覆盖，并限制其余定义格的污染； $*$ 格没有正确性约束。

对偶证书与自然版本的尺度

LP 对偶在每个定义格引入 $\mu_{xy}\ge0$ ，在目标格另引入 $\phi_{xy}\ge0$ 。目标为

(1-\varepsilon)\sum_{f(x,y)=z}\mu_{xy} -\sum_{f(x,y)=z}\phi_{xy} -\varepsilon\sum_{(x,y)\in D\setminus f^{-1}(z)}\mu_{xy},

每个矩形须满足

\sum_{R\cap f^{-1}(z)}(\mu-\phi) -\sum_{R\cap(D\setminus f^{-1}(z))}\mu\le1.

这些是非负 LP 权重，不要求归一化为概率；任何可行对偶目标都给出 primal 最优值的下界。

自然版本使用的是倒数质量，不是 corruption 页的负对数参数。对支撑在 $D$ 上的分布 $\lambda$ 、同一定义域上的函数 $g$ 和 $\rho>0$ ，令

B^z_\rho(g;\lambda) =\min_{R:\ e_z(R)<\rho g_z(R)}\frac1{g_z(R)}, \quad g_z(R)=\lambda(R\cap g^{-1}(z)),\quad e_z(R)=\lambda(R\cap(D\setminus g^{-1}(z))).

这里还固定 $\lambda(g^{-1}(z))\ge1/2$ ，所以存在正质量的纯净 singleton，最小值有定义。这个量和 $2^{\operatorname{corr}}$ 属于相同的倒数质量尺度；污染条件在这里是严格小于，和 corruption 页的非严格版本仍须区分。

对 $\delta>0$ ，记 $\widetilde{\operatorname{srec}}^z_{\rho,\delta}(f)$ 为所有上述 $\lambda,g$ 中、满足 $\lambda(f\ne g)<\delta$ 时 $B^z_\rho(g;\lambda)$ 的上确界；没有可行选择时约定为零。上确界避免对严格距离约束误称最优必定取得。Jain–Klauck 的 Lemma 2 给出，例如 $0<\varepsilon<1/4$ 时，

\operatorname{srec}^z_\varepsilon(f) \le\widetilde{\operatorname{srec}}^z_{\varepsilon/2,(1-\varepsilon)/2}(f), \qquad \operatorname{srec}^z_\varepsilon(f) \ge\frac12\left(\frac14-\varepsilon\right) \widetilde{\operatorname{srec}}^z_{2\varepsilon,\varepsilon/2}(f).

这组转换保留了两个不同的污染半径和修改质量，不能省略后把自然版本与 LP 数值视为相等。

对布尔 $f$ ，还可直接从 primal 验证一条明确的层级。取 $0\le\varepsilon<1/2$ 、 $\eta=2\varepsilon/(1-2\varepsilon)$ ；分别取两个输出的平滑矩形覆盖，相减得到 $h$ ，则每个定义格满足 $1-2\varepsilon\le(2f-1)h\le1$ 。除以 $1-2\varepsilon$ 就成为平滑 discrepancy的可行解。因此

\operatorname{sdisc}_\eta(f) \le\frac{2}{1-2\varepsilon}\operatorname{srec}_\varepsilon(f) \le\frac{2}{1-2\varepsilon}\operatorname{prt}_\varepsilon(f).

后一不等式来自对 partition LP 的可行解只保留某个输出标签；剩余权重满足该标签的平滑矩形约束。

直觉

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

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

每棵树至多有 $2^c$ 个叶，因此这组权重满足 $\sum_Rw_R\le2^c$ 。于是 $\operatorname{srec}_\varepsilon(f)\le2^c$ ，结合 $c\ge0$ 可写成 $c\ge\log_2\max\{1,\operatorname{srec}_\varepsilon(f)\}$ 。这是 LP 数值到通信 bit 数的必要对数转换；找到便宜的可行覆盖只给 LP 上界，证明通信下界需要证明所有可行覆盖都昂贵。

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

例子与边界

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

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

\operatorname{srec}^1_0(\mathrm{XOR}_1)=2.

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

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

推论与应用

平滑矩形界可由带 joker 的 corruption 界构造对偶证书：joker 质量以负号抵消少量坏区域，而对所有矩形成立的不等式阻止协议用许多近单色叶覆盖目标输入。它与平滑 discrepancy 和 partition bound 的比较遵循上面明确的参数缩放。

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

参考资料

Rahul Jain and Hartmut Klauck, “The Partition Bound for Classical Communication Complexity and Query Complexity”, Proceedings of CCC, 2010, pp. 247–258.
Hartmut Klauck, “A Strong Direct Product Theorem for Disjointness,” Proceedings of STOC, 2010, pp. 77–86.
Amit Chakrabarti, Ranganath Kondapally, and Zhenghui Wang, “Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming,” Proceedings of RANDOM, 2012, pp. 483–496.

形式陈述 ​

对偶证书与自然版本的尺度 ​

反向链接

形式陈述

对偶证书与自然版本的尺度