通信复杂度的 partition bound

一棵确定性协议树把输入空间划成带输出标签的矩形。public-coin 协议是这些树的分布，所以每个格被总概率一覆盖，其中至少 $1-\epsilon$ 的概率来自正确标签。LP 保留这两条全局一致性约束，却忘掉同一棵树中矩形必须真的组成一份整数划分，因而是协议的分数松弛。

它与确定性单色矩形划分数理路单色矩形划分数Monochromatic rectangle partition number用互不相交单色组合矩形划分通信矩阵，并刻画它与确定性通信复杂度之间从对数下界到二次对数上界的关系。不同：后者最小化一份零误差整数划分的块数；本页允许跨许多协议树叠加分数权重，并显式处理错误和 partial function。

对零误差二阶 XOR，任何含两个格的矩形都会同时含 $0$ 与 $1$，所以单色矩形只能是 singleton。取四个格各自的矩形，并给真实输出标签权重 $1$，得到可行解，目标值 $4$。

反向把四条正确性约束相加：每个带标签单色 singleton 至多服务一个格；零错误又不允许错误标签覆盖定义格，所以总权重至少 $4$。因此

恰给出两 bit 下界；Alice 发送输入、Bob 回传答案的两 bit 协议达到它。若只要求 Bob 输出并采用不把本地最终输出标签纳入 transcript 叶的另一 convention，必须同步修改通信树与 LP 接口，不能只把数值减一。

LP 把协议压成无顺序矩形权重，所以不能识别相同总通信下是谁先说、消息如何交替或用了几轮。这正是它与轮数—通信量权衡理路轮数—通信量权衡Round-communication tradeoff · Round-sensitive communication complexity固定消息条数、首发者、单消息预算与错误后，刻画增加交互如何降低完成同一通信任务的总 bit 数。的镜像边界：前者可给强 one-shot 下界，却不是 round-sensitive 参数。

对任一 partition primal 可行解，只保留输出 $z$ 的权重，便得到平滑矩形 LP理路平滑矩形界Smooth rectangle bound · Smooth corruption bound以单一输出标签的分数矩形覆盖允许少量目标扰动，形成介于 smooth discrepancy 与 partition bound 之间的一侧下界。的可行解：总覆盖为一保证目标格覆盖至多一；其他定义格已有至少 $1-\epsilon$ 的正确标签权重，故错误标签 $z$ 的权重至多 $\epsilon$。保留的目标和不超过原总和，因此

这是从较强 LP 的 primal 解到较弱 LP 的方向；用对偶证书证明相同支配时，转换方向相反。对平滑 discrepancy 的进一步比较还须使用平滑矩形页中明确的参数缩放。

该界适用于 relation 的推广并可导出 strong direct-product 结论，但错误事件是逐格协议错误还是联合输出错误必须与 LP 定义对齐。它仍是松弛：大值推出高通信，小值不保证存在对应协议树；round、information cost 和 coin 的实现细节都已在凸化时丢失。