通信复杂度的 Direct Sum 与 Direct Product

形式陈述

k 重任务

固定有限非空集合 $X,Y,Z$ 、函数 $f:X\times Y\to Z$ 与整数 $k\ge1$ ，并采用随机通信复杂度的硬通信上限和明确的输出约定。定义

f^{\otimes k}(x^k,y^k) =\bigl(f(x_1,y_1),\ldots,f(x_k,y_k)\bigr).

协议接收 $k$ 组输入并必须输出完整 $k$ 元答案。输入可以按乘积分布 $\mu^k$ 独立抽取，也可以做 worst-case 分析；“独立实例”描述分布时必须明确，笛卡尔输入元组本身不自动产生概率独立。

逐实例运行单份协议给出直接上界：通信乘 $k$ ，轮数若串行也乘 $k$ ，若并行则轮数可保持而每轮消息变长。这保留原来的每坐标错误上限 $\varepsilon$ ；由并集界，整批错误只能直接界为 $\min\{1,k\varepsilon\}$ 。Direct sum/product 问的是联合协议能否通过跨实例编码显著优于这种基线。

Direct sum 命题

Direct sum 关注资源总量。典型形式是

R_\varepsilon(f^{\otimes k}) \ge \Omega\!\left(k\,R_{\varepsilon'}(f)\right),

其中联合错误、逐坐标错误以及 $\varepsilon'$ 必须由定理指定。若只要求平均坐标错误小，协议可以牺牲少数实例；若要求整个输出向量全对，一次坐标错误就算总失败，二者不等价。

Direct sum 不是所有模型中从定义自动成立。批量输入可能共享结构、输出可以压缩，或通信协议能跨坐标编码；线性下界需要证明每个实例都消耗不可共享的信息。

在二方、确定性、总函数通信复杂度中，最强的经典形式也已经被反驳。它曾断言对任意函数族 $(f_n)$ ，存在常数 $C$ 使充分大的 $n,\ell$ 都满足

D(f_n^{\otimes\ell}) \ge \ell\bigl(D(f_n)-C\bigr).

Mackenzie 与 Saffidine 构造了总函数族，使每份实例可节省的 bit 数随规模无界；他们还得到某个常数 $\varepsilon>0$ 下

D(f_n^{\otimes\ell}) <(1-\varepsilon)\ell D(f_n)

的参数族。这否定的是“只容许每份损失一个固定加法常数”的强形式。常数比例的节省仍可能与某些较弱的 $\Omega(\ell D(f))$ 下界并存，因此不能把该反例写成所有 direct-sum 现象都失败；它也不推翻乘积分布下信息成本的张量化性质。

Information cost 的张量化

在乘积分布 $(X_i,Y_i)\stackrel{\mathrm{iid}}\sim\mu$ 下，设 transcript 为 $T$ 。链式法则把输入元组的信息泄露拆开，例如

I(X^k;T\mid Y^k,R) =\sum_{i=1}^k I(X_i;T\mid X_{<i},Y^k,R).

固定坐标 $i$ ，把真实输入 $(x,y)$ 放在该处。公开按边缘分布生成 $X_{<i}$ 与 $Y_{>i}$ ；Bob 私下按条件分布生成 $Y_{<i}\mid X_{<i}$ ，Alice 私下生成 $X_{>i}\mid Y_{>i}$ ，各填充坐标独立。再运行原协议，Bob 输出第 $i$ 个答案。新公共币记为 $Q_i=(R,X_{<i},Y_{>i})$ ，它独立于真实输入对。这样补齐的输入服从 $\mu^k$ ，但没有把本应私有的全部填充输入泄露给双方。[1]

若原协议的每坐标分布错误至多 $\rho$ ，构造的单副本协议也满足这个要求。其内部信息成本为

J_i=I(X_i;T\mid Y_i,Q_i)+I(Y_i;T\mid X_i,Q_i).

由于不同输入对独立， $X_i$ 在给定 $(Y_i,Q_i)$ 后仍与 $Y_{<i}$ 独立。先把 $Y_{<i}$ 加进观察量，再用链式法则，得到

I(X_i;T\mid Y_i,Q_i) \le I(X_i;T\mid Y^k,X_{<i},R).

对称地，把 $X_{>i}$ 加进第二项的观察量，得到

I(Y_i;T\mid X_i,Q_i) \le I(Y_i;T\mid X^k,Y_{>i},R).

对 $i$ 求和，第一组用正向链式法则，第二组用反向链式法则，便有

k\operatorname{IC}_\mu(f,\rho) \le\sum_{i=1}^kJ_i \le\operatorname{IC}^{\mathrm{int}}_{\mu^k}(\Pi).

最后用信息成本不超过通信，把信息 direct sum 转成通信下界。这里采用 Bob 输出与每坐标分布错误的口径；不能省去错误参数，再把结论理解成未注明模型的单次通信直接和。

条件变量不能随手删去：协议消息可把不同坐标相关起来，单项通常要在其他坐标或先前坐标上条件化。只写互信息“显然可加”会漏掉联合 transcript 的跨坐标依赖。

Direct product 命题

Strong direct product 进一步研究成功概率。其典型陈述是：对每个通信只有单份困难度 $o(k)$ 倍的协议，都存在一个输入元组，使同时正确输出全部 $k$ 个答案的概率至多

\exp(-\Omega(k)).

分布版本则对指定困难分布下的整批成功率给出同类界。输入上的量词必不可少：固定输出的零通信协议在某些输入上可以完全正确。这比相同模型下的 direct sum 更强，后者只排除固定成功率下过低的总通信。

错误事件相关使证明困难。若每份的实际错误率恰为 $\varepsilon$ ，且各次执行独立，全对概率为 $(1-\varepsilon)^k$ ；若只知道错误率至多 $\varepsilon$ ，这里只给出全对概率的下界。联合协议可以让所有错误高度相关，不能由单份错误机械乘法得到 converse。

直觉

Direct sum 问联合协议是否仍需为每份独立任务支付近似一份资源；direct product 更进一步，问资源低于这个线性预算时“全部答对”的概率是否指数崩塌。跨实例编码与相关错误使两者都不是把单份下界机械乘 $k$ ，信息链式法则提供了可张量化的账本。

例子与边界

向量 XOR 的线性图像

Alice 与 Bob 各持 $k$ bit 向量，要求公开输出逐坐标 XOR。Alice 发送 $x^k$ 的 $k$ bit，Bob 计算 $x^k\oplus y^k$ 并回传 $k$ -bit 输出，总通信 $2k$ 。

下界可直接从协议树证明，不限制协议先由谁说话。每片叶对应一个输出固定的矩形 $A\times B$ 。若 $B$ 非空，固定其中一个 $y$ ，映射 $x\mapsto x\oplus y$ 单射，所以 $A$ 至多含一个元素；对称地， $B$ 也至多含一个元素。全部 $2^{2k}$ 个输入对需要至少这么多叶子，树深度因而至少为 $2k$ 。所以上界达到精确最优值。

若只要求输出 XOR 的 parity， $k$ 个实例被聚合成一个 bit，协议只需双方各发送本地 parity。那已经不是 $f^{\otimes k}$ ，而是不同的组合函数；拿它反驳 direct sum 是更改输出任务。

推论与应用

参数与失败边界

在分布通信复杂度中，多实例分布若相关，其他坐标可能泄露目标坐标答案，信息张量化会失败。即使边缘都为 $\mu$ ，完美相关的 $k$ 份副本可能只需解决一次。

通信还可能采用 amortized 口径

\lim_{k\to\infty}\frac1k R(f^{\otimes k}),

它允许跨实例压缩的常数收益，不等于每个有限 $k$ 都有精确等式。Direct sum、amortized complexity 与 strong direct product 应分开命名。

最后，成功“每坐标至少 $2/3$ ”不推出“整个向量至少 $2/3$ ”。要保持联合成功率，朴素重复往往需把单份错误降到 $O(1/k)$ ，并支付额外 $\log k$ 放大；定理必须说明是否把这项成本算入基线。

参考资料

[1] Mark Braverman and Anup Rao, “Information Equals Amortized Communication,” IEEE Transactions on Information Theory 60(10), 2014, pp. 6058–6069。作者稿 Theorem 3.17 给出公开前缀／后缀与私下条件填充的坐标嵌入。
Rahul Jain, Hartmut Klauck, and Ashwin Nayak, “Direct Product Theorems for Classical Communication Complexity via Subdistribution Bounds,” STOC, 2008, pp. 599–608.
Thomas Holenstein, “Parallel Repetition: Simplifications and the No-Signaling Case,” Theory of Computing 5, 2009, pp. 141–172.
Simon Mackenzie and Abdallah Saffidine, “Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity,” STOC 2025, pp. 572–583; corrected arXiv v2, 14 April 2026；Conjecture 2.6 与 Theorem 2.7 明确强形式的量词。

形式陈述 ​

k 重任务 ​

Direct sum 命题 ​

Information cost 的张量化 ​

Direct product 命题 ​

向量 XOR 的线性图像 ​

参数与失败边界 ​