通信复杂度 lifting 定理

组合问题 ​

通信复杂度 lifting 不是一条对所有模型都通用的单公式，而是一族参数化定理：每个版本都要固定外层 query measure、两方通信模型、允许的错误与随机币、外层函数是否带 promise，以及 gadget 的宽度和伪随机条件。共同目标是把外层查询下界提升为组合函数的通信下界；具体损失和适用范围由所选版本决定。

令外层函数 $f:\{0,1{\}}^n\to Z$，gadget 为

$$g:X\times Y\to \{0,1\}.$$

Alice 持有 $x=(x_1,\dots ,x_n)\in X^n$，Bob 持有 $y=(y_1,\dots ,y_n)\in Y^n$。组合通信问题定义为

$$(f\circ g^n)(x,y)=f(g(x_1,y_1),\dots ,g(x_n,y_n)).$$

外层查询算法公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。只把中间 bit 串 $z_i=g(x_i,y_i)$ 当作 oracle；组合后，每次得知 $z_i$ 都要求 Alice 与 Bob 协同计算一份 gadget。

容易方向：模拟查询树 ​

若 $f$ 有一棵深度 $q$ 的确定性查询树，而 gadget $g$ 可用 $c_g$ bit 通信计算，双方可以逐步模拟：查询树请求索引 $i$ 时，运行 $g(x_i,y_i)$ 协议，把结果作为分支 bit，再继续下一节点。

总通信至多

$$q{c}_g$$

加上输出 convention 的常数成本。随机查询树也可在随机币模型对齐时模拟。这个方向只组合已有算法，不是 lifting theorem 的困难部分。

困难方向的典型形式 ​

Lifting theorem 试图证明反向：若 $f\circ g^n$ 有低通信协议，就能把它“降回”一棵浅的 $f$ 查询树。理想结论形如

$$\mathrm{CC}(f\circ g^n)=\mathrm{\Theta }(\mathrm{Query}(f)\cdot b(g)),$$

其中 $b(g)$ 是 gadget 的 bit 规模或单坐标通信尺度。精确常数、polylog 损失和可用的 query/communication measure 取决于具体定理。

证明通常维护一个仍可能的外层输入子 cube，并把通信协议的矩形逐步模拟成查询决策。Gadget 必须足够“大”、混合或伪随机，使一个大通信矩形不能对太多未查询坐标产生偏置；否则协议可能利用跨坐标结构，无法局部化为 query。

OR-of-AND 的组合图像 ​

取外层 $f={\mathrm{OR}}_n$，gadget $g(a,b)=a\wedge b$，其中 $a,b\in \{0,1\}$。组合函数为

$$\underset{i=1}{\overset{n}{\bigvee }}(x_i\wedge y_i),$$

也就是判断两份特征向量是否存在共同的 $1$。查询 OR 需要在最坏情形检查全部 $n$ 个中间 bit；逐 gadget 模拟给出 $O(n)$ 通信。

这个例子说明 composition 的语义，却不是通用 lifting theorem 的证明。常数大小 AND gadget 可能不满足某些 lifting 定理要求；该函数的线性下界可以由 Disjointness 专门方法得到。把“看起来是一位 query 对应一份 gadget”直接写成 $\mathrm{\Omega }(n)$，会跳过困难方向。

Gadget 参数为何不能省 ​

若 $g$ 是常值函数，$f\circ g^n$ 也成为常值，无论 $f$ 查询复杂度多高都没有通信下界。若 $g(x,y)$ 只依赖 Alice 输入，Alice 可以本地算出全部中间 bit，再按输出发送，模型同样失去平衡。

有效 gadget 需要让每个输出同时依赖双方，并在大行列子集上保持足够丰富。Index gadget、inner-product gadget 等常按块宽 $b=\mathrm{\Theta }(\log n)$ 选择；gadget 越大，单次模拟成本和矩形伪随机性同时变化。

模型专属性 ​

确定性 lifting、随机 lifting、非确定性 lifting 和量子 lifting 是不同定理。随机版本还要处理分布、错误与公共币；把确定性 query lower bound 无条件乘 gadget 宽，不能自动得到 bounded-error 通信下界。

外层 partial function 的 promise 必须由组合输入实现。协议可能利用 promise 在不同 gadget 坐标间的相关性；total-function 定理未必直接扩展。

Decision tree、parity decision tree、conical junta 等 query 模型也对应不同通信或证明系统。Lifting 不是从任意“查询下界”到任意“通信下界”的统一黑盒。

电路与证明复杂度接口 ​

通信下界可进一步嵌入电路、数据结构或证明系统：先把一个局部组件的行为写成两方协议，再用 lifting 后的通信困难排除小组件组合。每次转接都要保存 size、depth、fan-in 或 proof width 等参数。

因此 lifting 的价值在于模块化：外层函数提供清晰 query hardness，gadget 把 hardness 编码进更丰富模型。它不免除对 gadget simulation theorem 和后续模型归约的验证。

参考资料

• Mika Göös, Toniann Pitassi, and Thomas Watson, “Deterministic Communication vs. Partition Number,” FOCS, 2015, pp. 1077–1088.
• Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman, “Rectangles Are Nonnegative Juntas,” SIAM Journal on Computing 45(5), 2016, pp. 1835–1869.
• Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay, “Simulation Theorems via Pseudo-Random Properties,” Computational Complexity 28, 2019, pp. 617–659.