通信矩阵与组合矩形

从函数到通信矩阵 ​

对有限集合 $X,Y$ 上的函数 $f:X\times Y\to Z$，通信矩阵 $M_f$ 是以 Alice 输入 $x\in X$ 为行、Bob 输入 $y\in Y$ 为列的矩阵公理库矩阵Matrix以有限行列集合为索引、取值于半环，并以中间指标求和定义乘法的函数。：

$$M_f[x,y]=f(x,y).$$

矩阵不是一种新的算法，只是把所有输入对和正确输出同时摊开。行表示固定 Alice 所知后，答案怎样随 Bob 输入变化；列则作对称观察。交换双方角色会转置矩阵，但只要成本模型对称，问题的通信复杂度不因此改变。

对任意 $A\subseteq X$ 与 $B\subseteq Y$，集合

$$R=A\times B$$

称为组合矩形。它由可任意挑选的行集和列集组成；行、列无需在某种排序中连续。若 $f$ 在 $R$ 上恒等于 $z$，就称 $R$ 是 $z$-单色矩形。这里的“矩形”来自笛卡尔积公理库笛卡尔积Cartesian product · Direct product of setsA×B 是所有第一分量来自 A、第二分量来自 B 的有序对组成的集合。的闭合交叉，而不是平面图形的边界。

闭合交叉判据 ​

组合矩形有一个不依赖坐标次序的判据：若 $(x_0,y_0)$ 与 $(x_1,y_1)$ 属于 $R=A\times B$，那么交叉输入

$$(x_0,y_1),(x_1,y_0)$$

也必须属于 $R$。因为 $x_0,x_1\in A$ 且 $y_0,y_1\in B$，四种搭配没有理由缺失。反过来，对非空集合 $R\subseteq X\times Y$，若它对所有两点都满足这种交叉闭合，取其行投影 $A$ 与列投影 $B$，便有 $R=A\times B$。

这个判据是检查“看起来像一块区域”的集合是否真为矩形的可靠方法。矩阵中两个相隔很远的格子可以属于同一矩形，只要全部交叉格也被包含；两个相邻格也可能无法单独构成目标矩形，若它们的行列投影还强迫纳入不希望出现的交叉格。

Equality 矩阵中的非连续矩形 ​

令 $X=Y=\{00,01,10,11\}$，$f(x,y)=1$ 当且仅当 $x=y$。$M_f$ 的对角线为 $1$，其余位置为 $0$。取

$$A=\{00,11\},B=\{01,10\}.$$

$A$ 与 $B$ 在字典序中都不是连续区间，但 $A\times B$ 的四个输入对全部满足 $x\ne y$，因此这是一个 $0$-单色组合矩形。把它画在矩阵上会得到四个分散格；“分散”不妨碍其乘积结构。

相反，只取两个对角格

$$S=\{(00,00),(11,11)\}$$

并不是矩形。它的行、列投影都是 $\{00,11\}$，若 $S=A\times B$，就还必须含有 $(00,11)$ 与 $(11,00)$；这两个交叉格恰好缺失。$S$ 虽然是 $1$-单色集合，却不是单色矩形，说明“所有值相同”只是矩形下界工具的一半条件。

transcript 为什么切出矩形 ​

固定确定性协议的一条 transcript。Alice 在每个自己的结点只按 $x$ 和既有 transcript 选择下一 bit，因此她的消息只能筛选允许的行；Bob 的消息只能筛选允许的列。从 $X\times Y$ 开始逐步筛选，最终留下的输入集仍为某个 $A_t\times B_t$。完整归纳见协议树与 transcript公理库协议树与通信 transcriptProtocol tree · Communication transcript用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。。

如果协议正确计算 $f$，叶结点只有一个输出，于是 $A_t\times B_t$ 必须单色。所有可达叶的矩形两两不交，并覆盖整个 $X\times Y$，因为每个输入对沿确定规则到达唯一叶。这给出从通信协议到单色矩形划分的方向；反向从任意矩形集合构造低通信协议，则还需要能让双方逐步识别所属矩形，不能只靠“矩形数量很少”一句话完成。

对于关系问题，矩阵单元可能包含多个合法输出，而不是单一值。此时一个叶标记 $z$，只需保证其矩形内每个输入都允许 $z$。把关系任意选成某个函数代表再做矩阵，可能人为增加或减少困难；选择规则必须属于协议，而不能由分析者在看到完整 $(x,y)$ 后替双方决定。

边界与后续用途 ​

几何学中的轴对齐矩形依赖坐标上的顺序与区间，组合矩形只依赖集合乘积。即使 $X,Y$ 本身是数值集合，通信矩形中的 $A,B$ 也可以是任意子集。把组合矩形画成连续色块只是示意，不是定义。

矩形结构会支撑多种下界，但本页只建立共同接口：确定性 transcript 给出单色矩形。要从中导出具体 bit 下界，还需额外度量矩形的数目、可覆盖结构、代数秩或概率质量；这些方法的假设和误差模型不同，不能在定义页里用“矩形很多”笼统替代证明。

随机协议固定随机币后也得到矩形叶，但不同随机选择产生不同划分，而且单棵树可能有错误叶。因此确定性单色划分结论不能原样套用到允许错误的协议；需要结合输入分布和近单色条件重新计量。

矩阵表示还依赖输入编码。若同一抽象对象有不同私有输入划分，行列集合会改变，组合矩形族也随之改变。通信下界属于“函数加输入分割加协议模型”的整体，而不是脱离模型后只属于函数名字。

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapters 1–2.
• Tim Roughgarden, Communication Complexity (for Algorithm Designers), 2015, Lectures 1–3.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 1–4.