通信复杂度的 partition bound

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

它与确定性单色矩形划分数公理库单色矩形划分数Monochromatic rectangle partition number · Protocol 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 bound 支配平滑矩形界公理库平滑矩形界Smooth rectangle bound · Smooth corruption bound以单一输出标签的分数矩形覆盖允许少量目标扰动，形成介于 smooth discrepancy 与 partition bound 之间的一侧下界。，后者又支配 smooth discrepancy 与传统 rectangle/corruption 证据；证明方式是把较弱 LP 的可行解或对偶 witness 嵌入本页 LP。支配方向指“作为下界数值不弱”，不表示每个具体 dual certificate 都机械转换而无参数损失。

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