近似秩

形式陈述 ​

取有限非空指标集 $X,Y$。对通信矩阵理路通信矩阵与组合矩形Communication matrix · Combinatorial rectangle将两方函数排成输入行列矩阵，并以行集和列集的笛卡尔积刻画协议能够共同隔离的区域。或任意实矩阵 $A\in {\mathbb{R}}^{X\times Y}$ 和 $\epsilon \ge 0$，先在本页定义逐项最大范数

这不是最大行绝对和的诱导 ${\ell }_{\mathrm{\infty }}$ operator norm。$A$ 的 $\epsilon$-近似秩是在逐项误差约束内寻找最低实秩理路线性映射的秩Rank of a linear map · Matrix rank线性映射像空间的维数，表示其保留下来的独立输出方向数。，定义为

对 Boolean 通信矩阵常取常数 $0<\epsilon <1/2$；对 $\{\pm 1\}$ 符号矩阵则常取 $0<\epsilon <1$。约束是每个格都满足 $|A_{xy}-B_{xy}|\le \epsilon$，不是平均平方误差、谱范数误差或只在某个输入分布下高概率接近。显然 ${\mathrm{rank}}_0(A)=\mathrm{rank}(A)$，而放宽 $\epsilon$ 只会使最优秩不增。

若成本为 $c$ 的私有币协议以最坏错误 $\delta$ 计算 Boolean 矩阵 $M_f$，其接受概率矩阵 $P$ 满足 $\Vert P-M_f{\Vert }_{max}\le \delta$。

选择由公开消息前缀决定发言者和终止的标准私有币协议。私有随机带的因子分解理路信息复杂度Information complexity · Information cost of a protocol · Internal information cost · External information cost从私有随机带的因子分解证明信息成本界，完整计算 AND 协议的内部、外部、平均与最坏成本，并区分输出熵。说明，固定一条完整 transcript 后，其发生概率可分成只依赖 Alice 输入和只依赖 Bob 输入的两个因子；若 Bob 最终输出，可把接受条件一并计入 Bob 的因子。每条 transcript 对 $P$ 的贡献因此是一个外积。至多 $2^c$ 条 transcript 相加，得到 $\mathrm{rank}(P)\le 2^c$，从而

取最大值使零矩阵也得到下界 $0$。

无纠缠量子协议也让接受概率矩阵逐格逼近目标，但通信量与该矩阵秩之间的指数换算不同，不能沿用上式的系数。public-coin 情形则需计入 Newman 转换的输入长度与误差损失；直接对公共币种子取平均可能提高秩，不能无条件照搬私有币证明。