通信复杂度的 discrepancy 方法

分布下的矩形不平衡 ​

设 $f:X\times Y\to \{0,1\}$，$\mu$ 是输入对上的概率分布公理库概率分布Probability distribution · Law定义在可测空间上的概率测度；随机变量的律是由推前得到的一类分布。。定义符号矩阵

$$F(x,y)=(-1{)}^{f(x,y)}.$$

对组合矩形 $R=A\times B$，其带符号质量为

$${\mathrm{disc}}_{\mu }(f;R)=|\sum _{(x,y)\in R}\mu (x,y)F(x,y)|.$$

等价地，它是 $R$ 内 0-输入质量与 1-输入质量之差的绝对值。分布 discrepancy 取所有组合矩形公理库通信矩阵与组合矩形Communication matrix · Combinatorial rectangle将两方函数排成输入行列矩阵，并以行集和列集的笛卡尔积刻画协议能够共同隔离的区域。中的最大值：

$${\mathrm{disc}}_{\mu }(f)=\underset{R}{max}{\mathrm{disc}}_{\mu }(f;R).$$

值很小表示没有任何矩形能捕获大量偏向某个输出的概率质量。这里质量未条件化于 $R$；一个极小矩形即使内部完全单色，其绝对 discrepancy 仍可能很小。

从协议到相关性 ​

令确定性协议 $P$ 通信至多 $c$，叶矩形为 $R_1,\dots ,R_k$，$k\le 2^c$。把叶输出编码为 $G_P(x,y)\in \{-1,+1\}$，正确时 $F{G}_P=1$，错误时为 $-1$，因此

$${\mathbb{E}}_{\mu }[F{G}_P]=1-2{\mathrm{err}}_{\mu }(P,f).$$

$G_P$ 在每个叶矩形上为常数 $g_j$。展开划分有

$${\mathbb{E}}_{\mu }[F{G}_P]=\sum _{j=1}^k{g}_j\sum _{(x,y)\in R_j}\mu (x,y)F(x,y).$$

由三角不等式，每项绝对值至多 ${\mathrm{disc}}_{\mu }(f)$，所以

$$1-2{\mathrm{err}}_{\mu }(P,f)\le 2^c{\mathrm{disc}}_{\mu }(f).$$

若错误至多 $\epsilon <1/2$，立即得到

$$c\ge {\log }_2\frac{1-2\epsilon }{{\mathrm{disc}}_{\mu }(f)}.$$

对 worst-case bounded-error 随机协议，先在 $\mu$ 下平均、再固定一条错误不增的随机带，便回到上述确定性协议。因此同一式子也是 $R_{\epsilon }^{\mathrm{pub}}(f)$ 的下界。

内积函数的谱计算 ​

令 $X=Y=\{0,1{\}}^n$，$f(x,y)=⟨x,y⟩mod2$，$\mu$ 为均匀分布。设 $N=2^n$，符号矩阵 $H_{x,y}=(-1{)}^{⟨x,y⟩}$ 是 Walsh–Hadamard 矩阵，并满足

$$H{H}^{\mathsf{T}}=NI.$$

对矩形 $A\times B$，带符号总和是 $1_A^{\mathsf{T}}H{1}_B$。由Cauchy–Schwarz 不等式公理库Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。和 $H$ 的谱范数 $\sqrt{N}$，

$$|1_A^{\mathsf{T}}H{1}_B|\le \Vert 1_A{\Vert }_2\Vert H{1}_B{\Vert }_2\le \sqrt{|A|}\sqrt{N|B|}\le N^{3/2}.$$

均匀分布给每格质量 $1/N^2$，故

$${\mathrm{disc}}_{\mu }(f)\le N^{-1/2}=2^{-n/2}.$$

代入下界，在固定 $\epsilon <1/2$ 时得到 $R_{\epsilon }^{\mathrm{pub}}(f)\ge n/2-O(1)$。这条计算没有枚举协议，只证明所有矩形在均匀分布下都近乎平衡。

如何使用该方法 ​

第一步选分布 $\mu$；均匀分布并非总是最难。第二步对任意行集 $A$、列集 $B$ 控制带符号和，常借助谱范数、Fourier 系数或几何不等式。第三步确认目标协议错误与通信采用上面相同量词，再代入相关性式。

若只估计某一类“规则矩形”，下界不能覆盖一般协议叶；组合矩形允许任意子集 $A,B$。若估计的是条件偏差

$$|\text{Pr}[f=0\mid R]-\text{Pr}[f=1\mid R]|,$$

还要乘 $\mu (R)$ 才是本页 discrepancy。

与其他 discrepancy 的边界 ​

数值积分和低差异序列中的 star discrepancy 比较点集落入锚定几何盒的频率与体积；本页比较通信矩形中的 0/1 符号质量。两者都叫 discrepancy，却拥有不同测试集合、基准测度和用途。

Discrepancy 对正负质量做抵消，适合双侧错误下的相关性下界。一个矩形内部有轻微偏向但质量巨大，或偏向极强但质量极小，都由乘积效果共同决定；corruption 方法则更直接排除大而近单色的矩形，参数不能不经转换混用。

最后，小 discrepancy 是充分的下界证据，不是通信困难的必要刻画。某些函数随机通信很高而 discrepancy 下界不紧；方法失败不等于存在低通信协议。

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Chapter 3.
• László Babai, Noam Nisan, and Mario Szegedy, “Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs,” Journal of Computer and System Sciences 45(2), 1992, pp. 204–232.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 4.