技术摘要：零误差信息等于摊销通信复杂度

1. 问题陈述

本文探讨了随机通信复杂度中的直接和问题（direct sum problem）。核心问题在于：解决 $n$ 个独立的计算任务 $f$ 的实例，究竟是必然需要解决单个实例所需资源的 $n$ 倍，还是可以通过“摊销（amortization）”实现节省？具体而言，本文研究了在全局误差模型（即 $n$ 个实例的总误差概率被限制在 $\varepsilon$ 以内）下，$n$ 个关系 $f$ 的随机通信复杂度 $R_\varepsilon(f^n)$ 的渐近行为。

虽然之前的研究已经证明，在逐实例误差模型（即每个实例必须满足误差 $\le \varepsilon$）下，直接和猜想是不成立的，但该猜想在标准的全局误差模型下的状态仍然悬而未决。本文旨在确定精确的渐近极限：
$$\lim_{n \to \infty} \frac{R_\varepsilon(f^n)}{n}$$

2. 方法论

作者结合了信息论工具和新颖的协议构建方法，以建立紧致的上下界。

2.1 核心概念

• 零误差信息复杂度 ($IC_0(f)$)： 定义为以零误差计算 $f$ 所需的最小信息成本，并在所有输入分布上取最大值。
• 分布信息复杂度： 衡量在特定输入分布 $\mu$ 下，协议转录（transcript）所揭示的信息量。
• 非对称信息复杂度： 一种专门针对单侧误差约束（侧重于支持在 0-输入上的分布）设计的专门度量（$IC^{U_0}_{FP=0, FN \le \varepsilon}$）。

2.2 关键技术创新

• 前缀验证嵌入（Prefix-Verification Embedding）： 为了证明下界，作者引入了一种新的单实例协议嵌入方法。不同于难以定位全局误差的标准嵌入，该方法允许 Alice 和 Bob 在均匀随机选择的一个坐标 $I$ 上模拟一个 $n$ 实例协议 $\Pi_n$。至关重要的是，Bob 在模拟过程中会主动验证前缀（所有实例 $< I$）的正确性。
  • 如果前缀正确，则继续模拟。
  • 如果检测到前缀错误，Bob 发送“中止（Abort）”信号。
  • 这种机制确保了单实例误差被降低到 $O(\varepsilon/n)$，同时将中止概率限制在全局误差 $\varepsilon$ 以内。这使得作者能够将 $n$ 个实例的摊销成本与单个实例的零误差信息复杂度联系起来。
• 概率切换与压缩（Probabilistic Switching and Compression）： 对于上界，作者将标准的交互式消息压缩技术（将通信量减少以匹配信息成本）与一种概率切换策略相结合。该协议要么以概率 $\varepsilon$ 立即停止，要么以概率 $1-\varepsilon$ 模拟 $n$ 个最优零误差协议。
• 组合的两步策略： 对于函数的组合（特别是 $OR_n \circ f$），作者利用了“随机抽样”随后“评估偏斜输入”的策略。这使得他们能够处理假阳性和假阴性的不对称性，通过在初始样本中不存在正向坐标的条件下对输入分布进行约束。

3. 关键贡献与结果

3.1 期望复杂度精确表征

本文建立了全局误差界 $\varepsilon$ 下期望随机通信复杂度的精确渐近极限。
定理 1： 对于任何 $\varepsilon \in (0, 1)$ 和关系 $f$：
$$\lim_{n \to \infty} \frac{R_\varepsilon(f^n)}{n} = (1 - \varepsilon) IC_0(f)$$
这一结果表明，摊销成本是由零误差信息复杂度而非 $\varepsilon$-误差信息复杂度决定的。因子 $(1-\varepsilon)$ 的出现是因为协议可以承担以 $\varepsilon$ 的概率中止（或失败），从而有效地降低了“有效”通信负载。

3.2 最坏情况摊销复杂度界限

基于期望情况，作者推导了标准最坏情况随机通信复杂度的紧致界限。
定理 2：
$$(1 - \varepsilon) IC_0(f) \le \liminf_{n \to \infty} \frac{R_\varepsilon(f^n)}{n} \le \limsup_{n \to \infty} \frac{R_\varepsilon(f^n)}{n} \le IC_0(f)$$
推论 1： 摊销最坏情况复杂度为 $\Theta(IC_0(f))$。
这证实了在搜索问题（关系问题）下，直接和猜想（形式为 $\Omega(n \cdot R_\varepsilon(f)) = R_\varepsilon(f^n)$）在全局误差模型下是不成立的，因为由于先前工作 [GKR16a] 中建立的信息与通信复杂度之间的指数级分离，其摊销成本严格小于 $n \cdot R_\varepsilon(f)$。然而，本文明确指出，目前尚不清楚这种失效是否也适用于全函数（total functions），因为目前尚未发现此类分离。

3.3 单侧误差与函数组合

作者将技术扩展到严格单侧误差约束（零假阳性、有界假阴性）下的组合 $OR_n \circ f$。
定理 3：
$$\lim_{n \to \infty} \frac{R_{FP=0, FN \le \varepsilon}(OR_n \circ f)}{n} = IC^{U_0}_{FP=0, FN \le \varepsilon}(f)$$
这提供了一个精确的表征，其极限由定义在支持 0-输入上的特殊非对称信息复杂度度量所控制。

3.4 对集合不相交问题猜想的反驳

通过将定理 3 应用于集合不相交问题（$DISJ_n$，即 $OR_n \circ \text{AND}$），本文解决了文献 [DFHL18] 中的一个开放猜想。

• 猜想 [DFHL18]： 提出标准随机通信规模为 $n \cdot IC^{U_0}_{FP=0, FN \le \varepsilon}(\text{AND}) + o(n)$。
• 反驳： 作者表明，正确的缩放是由非对称度量 $R_{FP=0, FN \le \varepsilon}$ 控制的，而非标准的双侧有界误差 $R_\varepsilon$。他们指出，对于集合不相交问题，标准复杂度在 $\varepsilon = 1/2$ 时平凡地消失，而所提议的信息复杂度度量仍保持严格正值，从而证明了该猜想是错误的。

4. 意义与主张

本文声称解决了随机通信复杂度中直接和猜想的一个核心形式。其主要意义在于：

1. 精确表征： 首次提供了全局误差模型下摊销随机通信复杂度的精确渐近表征，将其精确地与零误差信息复杂度联系起来。
2. 结构性洞察： 引入了“前缀验证”嵌入机制，为在交互式协议中定位全局误差提供了一种更精细的工具，从而产生精确的结果而非仅仅是界限。
3. 解决开放问题： 成功反驳了关于集合不相交问题缩放行为的特定猜想，澄清了在摊销设置中标准双侧误差与单侧误差之间的区别。

作者强调，虽然直接和定理在搜索问题的一般意义上是不成立的（由于信息与通信复杂度之间的差距），但他们的工作精确地量化了通过摊销可实现的“节省”，并表明它完全由基础函数的零误差信息成本决定。他们进一步澄清，目前已确立了直接和定理在全局误差模型下对搜索问题失效，而全函数的情况仍是一个开放问题。