分解范数通信下界

随机协议是确定性协议矩阵的凸组合。秩不具凸性，平均许多低秩矩阵可变成满秩；${\gamma }_2$ 是范数，三角不等式让平均后的复杂度仍受每个协议树控制。再把平均输出的常数偏置缩放到乘法 margin $1$，就得到合法近似分解。

这条路线把难处理的近似秩公理库近似秩Approximate rank · Entrywise approximate rank在逐项最大绝对误差约束内寻找最低实秩矩阵，量化通信矩阵可被低维实矩阵近似的程度。换成可由 SDP 逼近的凸松弛。它也给出一条实际使用近似秩的交叉校验：Krause 的私有币下界和

直接推出同一个 $2\log {\gamma }_2^{\alpha }-2\log \alpha$ 私有币下界；正文的凸组合证明则进一步直接处理 public coins，而不先支付 Newman 转换损失。

对二阶 XOR 符号矩阵

取 $u=(1,-1{)}^{\mathsf{T}}$、$v=(1,-1{)}^{\mathsf{T}}$，最大行范数均为 $1$，故 ${\gamma }_2(S)=1$。对任意 $\alpha \ge 1$，$B=S$ 合法，从而 ${\gamma }_2^{\alpha }(S)=1$；下界只给 $-2\log \alpha$，截成零后无信息。这与 XOR 的常数通信完全相容，也明确展示通用方法可以不紧。

若误把 $B$ 的约束写成 $\Vert S-B\Vert$ 的谱误差，协议平均矩阵不再逐格保证合法；若去掉上界 $S_{xy}{B}_{xy}\le \alpha$，得到 $\alpha =\mathrm{\infty }$ 的 margin 版本，参数和结论都改变。对于 additive entrywise 近似秩，可用 $B\mapsto B/(1-\epsilon )$ 在符号矩阵、$\epsilon <1$ 时转换参数，但不能把两种定义写成同一个符号而不说明缩放。

对常数 $\alpha >1$，近似秩与 ${\gamma }_2^{\alpha }$ 存在带矩阵尺寸对数因子的多项式关系，因此分解范数是近似秩的可计算凸代理。其 SDP 对偶会产生带权矩阵见证，并通向平滑 discrepancy公理库平滑 discrepancySmooth discrepancy · Smoothed generalized discrepancy允许目标函数在小概率质量上平滑改变，再以 discrepancy 的 LP 对偶证书给出更稳健的通信下界。。

定理只给 lower bound：小 ${\gamma }_2^{\alpha }$ 不自动构造低通信协议。它也把所有固定币协议树压成矩阵平均，因而忘掉 round、每方消息配额与 transcript 信息量；这些资源需要轮消除或信息复杂度工具单独分析。