带 joker 的 corruption 界

三种分布以带符号矩形不等式共同计账，互不相交协议叶只支付一次 joker 总质量 — 带 Joker 的 Corruption 全局预算

形式陈述

在普通 corruption 界的二方矩形设置中，设 partial function $f:X\times Y\to\{0,1,*\}$ ， $A_i=f^{-1}(i)$ 。取三个概率分布 $\mu_0,\mu_1,\mu_+$ 、正常数 $\alpha_0,\alpha_1,\alpha_+$ 与 $m>0$ 。取 $0\le\eta<1$ ，假设 $\mu_i(A_i)\ge1-\eta$ （ $i=0,1$ ），且对每个组合矩形 $R$ 都有

\alpha_1\mu_1(R)-\alpha_+\mu_+(R) \le \alpha_0\mu_0(R)+2^{-m}.

若

\eta<\frac{\alpha_1-\alpha_+}{\alpha_0+\alpha_1},

则存在只依赖这些常数的 $\varepsilon'>0$ 与 $\beta\in\mathbb R$ ，使分布通信复杂度在困难分布

\nu=\frac{\alpha_0\mu_0+\alpha_1\mu_1}{\alpha_0+\alpha_1}

下有 $D^\nu_{\varepsilon'}(f)\ge m+\beta$ ，从而公共币硬成本也满足 $R^{\mathrm{pub}}_{\varepsilon'}(f)\ge m+\beta$ 。这里采用分布通信页的承诺域约定：错误为 $\Pr_\nu[f(x,y)\ne *\ \land\ P(x,y)\ne f(x,y)]$ ，承诺外质量不计错，也不条件化删去； $\mu_0,\mu_1$ 因而仍可在未定义格上有至多 $\eta$ 的质量。 $\mu_+$ 不必支持在 $*$ 格；“joker”表示其质量在证书中带负号、输出可不被主困难分布计分，而不是修改协议的合法输入。

误差余量的明确选择

令 $q=\alpha_1-\alpha_+-(\alpha_0+\alpha_1)\eta>0$ 。对分布错误至多 $e$ 、成本 $c$ 的公开叶协议，将全部 $1$ -叶相加后，近似支撑条件与错误定义给出

2^{c-m}\ge q-(\alpha_0+\alpha_1)e.

因此可具体取 $\varepsilon'=q/[2(\alpha_0+\alpha_1)]$ 、 $\beta=\log_2(q/2)$ 。这个式子把未定义格和错颜色的至多 $\eta$ 质量都计入同一损失预算，并未加强原分布的支撑要求。

直觉

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

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

例子与边界

取精确支撑 $\eta=0$ ，并设 $\alpha_0=1,\alpha_1=2,\alpha_+=1$ 。假设对所有矩形有

2\mu_1(R)-\mu_+(R)\le\mu_0(R)+2^{-m}.

采用公开叶输出的协议树，成本 $c$ 的确定性协议至多有 $2^c$ 个互不相交 $1$ -叶，其并记为 $S_1$ 。逐叶求和并用 $\mu_+(S_1)\le1$ 得

2\mu_1(S_1)-1\le\mu_0(S_1)+2^{c-m}.

若两类条件错误都至多 $1/10$ ，则 $\mu_1(S_1)\ge9/10$ 、 $\mu_0(S_1)\le1/10$ ，所以 $0.7\le2^{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；其主要技术工作是为三种精心选择的分布证明全矩形不等式，而不是上述叶求和代数。该证书可嵌入平滑矩形界的对偶，因此是一种更易手算的 sufficient condition。

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

参考资料

Amit Chakrabarti and Oded Regev, “An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance,” SIAM Journal on Computing 41(5), 2012, pp. 1299–1317.
Rahul Jain and Hartmut Klauck, “The Partition Bound for Classical Communication Complexity and Query Complexity,” Proceedings of CCC, 2010, pp. 247–258.
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.

形式陈述 ​

误差余量的明确选择 ​

反向链接

形式陈述

误差余量的明确选择