通信复杂度的 Direct Sum 与 Direct Product

k 重任务

对函数 $f:X\times Y\to Z$ ，定义

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$ ，若并行则轮数可保持而每轮消息变长。Direct sum/product 问的是联合协议能否通过跨实例编码显著优于这种基线。

Direct sum 命题

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

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

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

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\sim\operatorname{Unif}[k]$ 嵌入一份单实例协议，并用公共随机性生成其余坐标，可把第 $i$ 项解释为解决一份 $f$ 所泄露的信息。适当的错误继承后得到

\operatorname{IC}_{\mu^k}(f^{\otimes k}) \ge k\operatorname{IC}_\mu(f)

这一类张量化结论。再用信息成本不超过通信，把信息 direct sum 转成通信下界。

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

Direct product 命题

Strong direct product 进一步研究成功概率。其典型陈述是：若通信只有单份困难度的 $o(k)$ 倍，那么同时正确输出全部 $k$ 个答案的概率至多

\exp(-\Omega(k)).

这比 direct sum 强。Direct sum 只排除在固定成功率下过低总通信；direct product 还说明资源不足时不是“稍微多错”，而是全对概率快速崩塌。

错误事件相关使证明困难。逐份独立运行错误率 $\varepsilon$ 的协议，若随机币独立，全对概率为 $(1-\varepsilon)^k$ ；但联合协议可以让所有错误高度相关，不能由单份错误机械乘法得到 converse。

向量 XOR 的线性图像

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

输出本身有 $k$ bit，且在 Alice 固定输入后随 Bob 输入遍历全部 $2^k$ 种向量；公开 transcript 必须区分这些答案，所以回传阶段至少要有 $k$ bit。对称地，Bob 要正确计算也需从 Alice 获得 $k$ bit 信息。这个任务的 direct sum 线性增长可由视图直接看见。

若只要求输出 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$ 放大；定理必须说明是否把这项成本算入基线。

参考资料

Mark Braverman and Anup Rao, “Information Equals Amortized Communication,” IEEE Transactions on Information Theory 60(10), 2014, pp. 6058–6069.
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.

k 重任务 ​

Direct sum 命题 ​

Information cost 的张量接口 ​

Direct product 命题 ​