通信复杂度的 discrepancy 方法

采用公开叶输出的协议树理路协议树与通信 transcriptProtocol tree · Communication transcript用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。，令确定性协议 $P$ 通信至多 $c$，叶矩形为 $R_1,\dots ,R_k$，$k\le 2^c$。把叶输出编码为 $G_P(x,y)\in \{-1,+1\}$，正确时 $F{G}_P=1$，错误时为 $-1$，因此

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

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

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

对 worst-case bounded-error 随机协议，使用固定分布下的平均论证理路分布通信复杂度Distributional communication complexity固定输入分布后，以确定性协议在该分布下的平均错误衡量通信，是随机最坏复杂度的分布侧接口。，先在 $\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 矩阵，并满足

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

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

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

如何使用该方法 ​

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

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

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

与其他 discrepancy 的边界 ​

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

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

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