单色矩形划分数 | Codeboy's Blog

形式陈述

划分数

设 $f:X\times Y\to Z$ ，其中 $X,Y,Z$ 有限非空。单色矩形划分是一族组合矩形

\mathcal R=\{A_1\times B_1,\ldots,A_k\times B_k\},

满足：每个矩形上 $f$ 恒定；不同矩形两两不交；所有矩形的并恰为 $X\times Y$ 。最少块数记为

\chi(f)=\min_{\mathcal R}|\mathcal R|.

行集 $A_j$ 和列集 $B_j$ 不要求在任何排列下连续。划分要求每个输入对恰好属于一块；允许重叠、只覆盖某一种输出的 rectangle cover 是另一种对象。

初等夹逼

本页把 $D^{\mathrm{cc}}(f)$ 定义为公开 transcript、公开叶标签的确定性 bit 通信复杂度：协议结束时，完整 transcript 确定一个带输出标签的叶，因此双方都能识别结果。若 $Z$ 的输出采用固定长编码，令

\ell_Z=\lceil\log_2|Z|\rceil.

则对任意有限输出函数都有

\boxed{ \lceil\log_2\chi(f)\rceil \le D^{\mathrm{cc}}(f) \le \chi(f)+\ell_Z }.

下界来自协议叶：成本至多 $c$ 的二叉协议树至多有 $2^c$ 个可达叶，每个叶输入集都是单色矩形，并且这些叶矩形互不相交、覆盖全部输入。因此

\chi(f)\le 2^c.

上界来自一个明确但粗糙的协调协议。给最优划分的矩形编号 $1,\ldots,k$ ，Alice 发送长度 $k$ 的成员向量

u(x)_j=\mathbf 1[x\in A_j].

Bob 根据自己的 $y$ 找到唯一满足 $u(x)_j=1$ 且 $y\in B_j$ 的编号，再发送该矩形的输出标签。划分保证这个编号存在且唯一，通信为 $k+\ell_Z$ 。这个协议没有把矩形划分直接当作协议树，而是为“双方如何找到所在块”支付了 $k$ 位协调成本。

Boolean 情形的经典强化

当 $f:X\times Y\to\{0,1\}$ 时，Aho–Ullman–Yannakakis 的经典结果把线性上界大幅改进为

D^{\mathrm{cc}}(f) =O\!\left((\log_2\chi(f))^2\right).

一种理解路径是引入 0、1 两侧的最小单色 rectangle cover。划分本身分别给出两侧 cover，所以相应的非确定性通信复杂度都至多 $\log_2\chi(f)+O(1)$ ；经典确定性模拟再给出

D^{\mathrm{cc}}(f)=O\bigl((N^0(f)+1)(N^1(f)+1)\bigr),

当 $\chi(f)\ge2$ 时即得到二次对数界； $\chi(f)=1$ 则函数恒定，公开输出也无需通信。两个加一项保留了本页的“只计证书长度”约定：例如 $f(x,y)=x_1$ 的两侧各由一个矩形覆盖，故 $N^0=N^1=0$ ，但公开计算仍需一 bit。这个反向模拟是非平凡定理：一般划分的矩形编号既不能由 Alice 单独从 $x$ 决定，也不能由 Bob 单独从 $y$ 决定，所以不能把 $k$ 块任意划分机械地压成深度 $\lceil\log_2 k\rceil$ 的协议树。

二次对数上界在一般情形已接近最优：存在 Boolean 函数族满足

D^{\mathrm{cc}}(f) =\Omega\!\left((\log\chi(f))^{2-o(1)}\right).

因此 $\log\chi(f)$ 是普适下界，却可能比真实确定性通信复杂度小接近一个平方。

直觉

协议到划分的方向很直接。固定 transcript 后，Alice 的每一步只按 $x$ 过滤行，Bob 的每一步只按 $y$ 过滤列，最终剩余输入天然是 $A\times B$ ；同一公开叶只能带一个输出标签，所以该矩形必须单色。

划分到协议的方向包含分布式定位困难。外部观察者看到 $(x,y)$ 后知道它属于哪块，但 Alice 只看到行、Bob 只看到列。块数少只说明答案空间的组合描述短，不自动说明双方能用同样短的交互找到那份描述。初等成员向量协议逐块报告 Alice 的可能性；AUY 定理则利用 0、1 cover 的结构反复缩小候选集合，才把成本降到多对数级。

例子与边界

二位 XOR

令 $X=Y=\{0,1\}$ ， $f(x,y)=x\oplus y$ 。通信矩阵是

\begin{pmatrix} 0&1\\ 1&0 \end{pmatrix}.

任意含两个格子的组合矩形要么取同一行、同一列，要么因矩形闭合同时包含四个交叉格；这些候选都不是单色。因此每个单色矩形至多含一个格， $\chi(f)=4$ ，对数下界给出 $D^{\mathrm{cc}}(f)\ge2$ 。

在本页的公开叶口径下，Alice 发送 $x$ ，Bob 计算 $x\oplus y$ 并把结果发回，共 2 位，因而下界取等。若另采用“只要求 Bob 输出”的模型，最后一位可以省略；两种常见定义只差常数，却会改变这种微型例子的精确数值，所以页面必须先固定 convention 再谈等号。

Partition 与 cover

一个 1-rectangle cover 只要求每个 1-输入至少落入一块，矩形可以重叠，也不必处理 0-输入。同一输入拥有多份证书并不妨碍非确定性验证，却不能直接成为确定性协议叶的唯一归属。把 cover 大小误作 $\chi(f)$ ，会丢掉“不重叠”和“覆盖全部输出”两项约束。

反过来，单色划分也不必是某棵协议树的叶划分。协议树的每次二分必须由当前发言者只根据自己的输入和既有 transcript 决定；任意组合矩形划分通常不满足这种递归可分性。若文献使用 protocol partition number，应核对它究竟指任意单色划分，还是要求能由协议递归产生的叶划分；本页的 $\chi(f)$ 固定采用前者。

推论与应用

单色矩形划分数给出确定性通信复杂度的组合下界，并与非确定性通信复杂度的 cover 量形成清晰对照。它说明“矩阵能被少量简单块描述”与“双方能低通信地协同定位块”之间仍隔着一层协议结构。

秩下界、fooling set、discrepancy 和 partition bound 也从通信矩阵提取下界，但使用的对象分别是线性代数分解、特殊输入集合、分布不平衡和加权矩形优化。比较这些量时，应先核对矩形是否要求单色、是否允许重叠、是否覆盖整张矩阵，以及结论针对确定性、非确定性还是随机通信。

参考资料

Alfred V. Aho, Jeffrey D. Ullman, and Mihalis Yannakakis, “On Notions of Information Transfer in VLSI Circuits,” STOC, 1983, pp. 133–139.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Sections 1.2–2.1.
Andris Ambainis and Mārtiņš Kokainis, “Almost Quadratic Gap between Partition Complexity and Query/Communication Complexity,” Electronic Colloquium on Computational Complexity, Report 200, 2015.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 1–2.

形式陈述 ​

划分数 ​

初等夹逼 ​

Boolean 情形的经典强化 ​

二位 XOR ​

Partition 与 cover ​

反向链接

形式陈述

划分数

初等夹逼

Boolean 情形的经典强化

二位 XOR

Partition 与 cover