第十章：通信复杂度

通信复杂度将输入拆分给多个参与者，并把本地计算视为免费。lower bound 因而只反映完成任务所需交换的信息量。

Two-party model

Alice 持有 $x\in X$，Bob 持有 $y\in Y$，目标是计算

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

确定性协议按轮发送 bit，每条消息可以依赖本地输入和此前 transcript。cost 是最坏输入上的总通信 bit 数：

$$D(f)=\min_\Pi\max_{x,y}|\Pi(x,y)|.$$

双方本地拥有无限计算能力，因此即使 $f$ 在单机上计算困难，也可能通信很少；反之，单机上简单的函数可能要求线性通信。

Protocol tree

确定性协议可表示为二叉树。内部节点指定发送方，分支由下一 bit 决定，叶节点给出输出。深度即最坏通信量。

每个 transcript 对应输入矩阵中的 combinatorial rectangle

$$A\times B\subseteq X\times Y.$$

原因是：固定 transcript 后，Alice 的一致输入集合只依赖 $x$，Bob 的一致输入集合只依赖 $y$。确定性协议的每个叶子必须是 monochromatic rectangle。

因此，若通信量为 $c$，输入矩阵至多被 $2^c$ 个 monochromatic rectangle 划分。通信 lower bound 可转化为 rectangle partition lower bound。

Equality

定义

$$\mathrm{EQ}(x,y)=1\iff x=y, \qquad x,y\in\{0,1\}^n.$$

确定性协议需要 $n+1$ 量级通信。矩阵对角线上的 $2^n$ 个 1 输入不能有两个落在同一 1-monochromatic rectangle，否则交叉输入也会被错误接受。

使用 public randomness 时，可以选择随机 hash，将 $x,y$ 映射到较短指纹。常数错误率只需 $O(1)$ 或 $O(\log 1/\varepsilon)$ 通信。该例说明随机化可指数降低通信量。

Fooling set

集合

$$S=\{(x_i,y_i)\}$$

是 1-fooling set，若所有 $f(x_i,y_i)=1$，且任意 $i\ne j$ 至少一个交叉输入 $(x_i,y_j)$、$(x_j,y_i)$ 输出 0。

任何 1-monochromatic rectangle 至多包含一个 $S$ 中元素，因此

$$D(f)\ge\log_2|S|.$$

fooling set 易于使用，但并非对所有函数都给出紧 lower bound。

Rank method

令 $M_f$ 为通信矩阵，元素为 $f(x,y)$。若一个 monochromatic rectangle 的指示矩阵 rank 为 1，而协议用至多 $2^c$ 个 rectangle 表示矩阵，则

$$D(f)\ge \log_2\operatorname{rank}(M_f)$$

（根据使用的域和输出表示作相应调整）。

rank 将组合划分转为线性代数对象。log-rank conjecture 研究确定性通信复杂度与矩阵 rank 的多项式关系，是该领域的重要问题。

Randomized communication

随机协议可使用 private coin 或 public coin。复杂度

$$R_\varepsilon(f)$$

要求对每个固定输入，协议对随机位的错误概率至多 $\varepsilon$。

Newman theorem 说明在有限输入长度下，public coin 相比 private coin 只节省约 $O(\log n)$ 通信。该结论需要额外传递少量信息来选择一个小随机样本集。

使用 Yao principle 证明 randomized lower bound：

1. 选择输入分布 $\mu$；
2. 证明任何低通信确定性协议在 $\mu$ 下错误较大；
3. 推出任意低通信随机协议存在某个输入错误较大。

Set Disjointness

Alice、Bob 分别持有集合的指示向量，判断是否存在位置 $i$ 满足 $x_i=y_i=1$。随机有界错误通信复杂度为

$$R(\mathrm{DISJ}_n)=\Omega(n).$$

该 lower bound 可用 corruption、discrepancy 或 information complexity 等方法证明。它是许多 streaming、distributed monitoring 和 data structure lower bound 的基础。

Information complexity

通信量计算 transcript 长度；information complexity 计算 transcript 对输入泄露的互信息。例如内部信息成本为

$$I(X;\Pi\mid Y)+I(Y;\Pi\mid X).$$

任何协议传输的 bit 数至少覆盖其信息成本。信息方法还允许 direct-sum：独立求解多个实例通常需要累加信息，从而解释批处理不能任意压缩。

从通信 lower bound 到其他模型

通信模型常嵌入其他计算过程：

• streaming：把输入流切成两段，算法内存状态作为 Alice 向 Bob 的消息；
• data structure：查询算法访问的 cell 与预处理数据形成通信协议；
• distributed computing：节点间消息本身就是通信；
• circuit：按变量划分线路，cut 上的信号形成协议。

归约需要精确说明一次查询、一个 memory cell 或一轮 streaming 对应多少通信 bit 和轮数。

本章自测

1. 为什么确定性协议的固定 transcript 对应 rectangle？
2. Equality 的随机协议为何不与确定性 lower bound 矛盾？
3. fooling set 如何限制 monochromatic rectangle 的覆盖？
4. Yao principle 中为什么只需分析确定性协议？
5. streaming 空间如何转化为通信消息长度？

上一章：随机化与平均复杂度 · 下一章：查询复杂度 →