形式陈述
Alice 知道输入 x y S x y ∈ { − 1 , 1 }
对实矩阵 B gamma-two 分解范数 公理库 gamma-two 分解范数 Gamma-two factorization norm · gamma_2 norm · Hilbert-space factorization norm 以实矩阵的 Hilbert 空间向量分解中最大行范数的最小乘积，定义可由半定规划计算的 gamma-two 范数。
γ 2 ( B ) = min B x y = ⟨ u x , v y ⟩ ( max x ‖ u x ‖ 2 ) ( max y ‖ v y ‖ 2 ) . 维数可以自由选择，优化的是两侧最大向量长度的乘积。给定 α ≥ 1
对 所 有 γ 2 α ( S ) = min { γ 2 ( B ) : 1 ≤ S x y B x y ≤ α 对所有 x , y } . 约束要求每个格符号正确、绝对值介于 1 α γ 2 α
对公共随机币通信复杂度 公理库 随机通信复杂度 Randomized communication complexity 允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。 0 ≤ ε < 1 / 2 α = ( 1 − 2 ε ) − 1
R ε pub ( S ) ≥ 2 log 2 γ 2 α ( S ) − 2 log 2 α . 通信量取所有输入和随机币结果上的最坏值。不同输出约定可能带来一个输出比特的差别；本页固定上述协议树约定，不把这个模型细节藏进公式。
直觉 固定随机币：协议树给出低复杂度矩阵
固定公共随机币 r c S ( r ) 通信记录 公理库 协议树与通信 transcript Protocol tree · Communication transcript 用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。 2 c
rank ( S ( r ) ) ≤ 2 c . 分解范数的一条标准不等式是
γ 2 ( M ) ≤ rank ( M ) ‖ M ‖ max , ‖ M ‖ max = max x , y | M x y | . 它是这里使用的几何工具，不是秩的定义。代入条目均为 ± 1 S ( r ) γ 2 ( S ( r ) ) ≤ 2 c / 2
对随机币平均：保留范数控制
令 P = E r S ( r ) e x y
S x y P x y = 1 − 2 e x y ∈ [ 1 − 2 ε , 1 ] . 这里出现 2 e x y + 1 − 1 2 B = α P 1 ≤ S x y B x y ≤ α
γ 2 α ( S ) ≤ γ 2 ( α P ) ≤ α E r γ 2 ( S ( r ) ) ≤ α 2 c / 2 . 取对数并整理，得到定理。固定币时用协议树，平均时用范数凸性，最后用正确率形成的数值间隙归一化 ，是整个证明的主线。
普通秩不能替代中间的范数：许多低秩矩阵的平均可以变成高秩矩阵。公共随机币正好引入了这种平均，因此仅凭“每个确定性协议矩阵都低秩”，推不出平均接受概率矩阵也低秩。
例子与边界 方法也可能给不出有效下界
对两比特 XOR 的符号矩阵
S = ( 1 − 1 − 1 1 ) = ( 1 − 1 ) ( 1 − 1 ) , 一维分解已使两侧最大向量长度都为 1 B γ 2 ( B ) ≥ ‖ B ‖ max ≥ 1 γ 2 α ( S ) = 1
一个真正增长的下界：内积模二
令 x , y ∈ { 0 , 1 } n S x y = ( − 1 ) x ⋅ y N = 2 n H H H T = N I α ≥ 1
γ 2 α ( H ) = N . 上界取 B = H H = H I N 1 B 1 ⟨ H , B ⟩ ≥ N 2 ‖ H ‖ 2 = N
‖ B ‖ ∗ ≥ N 3 / 2 . 其中 ‖ B ‖ ∗ B = U V T
‖ B ‖ ∗ ≤ ‖ U ‖ F ‖ V ‖ F ≤ N ( max x ‖ u x ‖ 2 ) ( max y ‖ v y ‖ 2 ) . 第二步只是把每侧 N N γ 2 ( B ) ≥ ‖ B ‖ ∗ / N ≥ N
R ε pub ( S ) ≥ n − 2 log 2 α . 对固定错误率，α n
推论与应用 与近似秩、半定规划的联系
若把相同乘法约束下的最低秩记为 rank α ( S )
rank α ( S ) ≥ ( γ 2 α ( S ) ) 2 α 2 . 这与近似秩 公理库 近似秩 Approximate rank · Entrywise approximate rank 在逐项最大绝对误差约束内寻找最低实秩矩阵，量化通信矩阵可被低维实矩阵近似的程度。 ‖ S − A ‖ max ≤ δ < 1 A / ( 1 − δ ) ( 1 + δ ) / ( 1 − δ )
计算上，可以寻找一个正半定块矩阵，其跨块条目为 B t t 平滑 discrepancy 公理库 平滑 discrepancy Smooth discrepancy · Smoothed generalized discrepancy 允许目标函数在小概率质量上平滑改变，再以 discrepancy 的 LP 对偶证书给出更稳健的通信下界。
对于固定 1 < α < ∞
本定理给的是通信下界 ，小范数本身不构造低通信协议。矩阵表示也没有保留轮数、消息顺序或每一方的单独预算。谱范数误差、平均误差、去掉幅值上界的纯符号约束，则各自改变可行域，不能沿用本页公式而不重新证明。
参考资料
Nati Linial and Adi Shraibman, “Lower Bounds in Communication Complexity Based on Factorization Norms ,” STOC , 2007，§3.1；扩展期刊版发表于 Random Structures & Algorithms 34, 2009, pp. 368–394。
Troy Lee and Adi Shraibman, Lower Bounds in Communication Complexity
Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman, “Complexity Measures of Sign Matrices,” Combinatorica 27, 2007, pp. 439–463，分解范数、秩与加权核范数之间的关系。
