本文研究差分隐私（DP）约束下的基础图优化问题，并给出基于“重构攻击”思路的新型下界证明。作者考虑图 G=(V,E,w⃗)，其中顶点集 V 与边集 E 是公开的，只有边权函数 w:E→ℝ 需要满足 ℓ1 邻接关系下的差分隐私。研究对象包括两个经典问题：发布最小生成树（MST）与发布最小权完美匹配。作者证明，在 n 个顶点、m>2n 条边的最坏情形图上，任何 DP 算法的误差下界为 Ω(n·log(m/n)/ε)。该下界与已知的纯 DP 算法上界相匹配，因此是紧的；并且即使在近似 (ε,δ)-DP 下，只要 δ ≤ (n/m)^{Ω(1)}，下界依然成立。这一结果改进了 Sealfon（PODS'16）给出的 Ω(n/ε) 下界，量级上增加了 log(m/n) 这个因子。 论文的一个重要对照结论是：在 ℓ1 邻接关系下，允许近似 DP 并不能降低 MST 的误差，这与 Pagh 等人（PODS'25）在 ℓ∞ 邻接关系下证明的“近似 DP 可大幅改善误差”形成鲜明反差，说明邻接关系（敏感度定义）的选择对可实现的效用具有决定性影响。作者并未局限于最坏情形图，而是进一步给出了具有扩展性质（expander）的一大类稀疏图上的下界；特别地，对任意最小割至少为 Ω(log n) 的图，证明了 MST 的 Ω(n/ε) 下界。 最后，作者把方法拓展到隐私层次聚类问题：在 Dasgupta 代价函数（STOC'16）框架下，给出首个由“平衡割的最小权重”参数化的近似 DP 下界，将 Deng 等人（ICLR'25）的结果推广到一般图，并推广到近似 DP 设置。核心方法属于重构式下界证明技术，通过论证若算法精度过高则攻击者可重构出受保护的权重信息，从而反推出误差不可避免。总体贡献是给出了图优化在 DP 下更强、更贴合图结构的误差刻画，明确了隐私—效用权衡的理论极限。

本文研究多参与方容错共识问题，特别关注一般性（非阈值）对手模型下的通信复杂度下界。作者基于有限射影几何构造了一个无限族 Z_proj^{n,d} 的对手结构，该结构满足 Q^d 条件（即任意 d 个对手集合的并集不覆盖全部参与者）。对于这类对手结构，作者证明：在无错误、R 轮协议中，实现 L 比特输入的交互一致性（interactive consistency）需要 Ω(L·n^{2+1/d}) 比特的期望通信量；而拜占庭同意（byzantine agreement）和广播（broadcast）则需要 Ω(L·n^{1+1/d}) 比特。在异步网络中，可靠广播和拜占庭同意也需要 Ω(L·n^{1+1/d}) 比特的期望通信量。此外，相关构造 Z_2-proj^{n,d} 使核心集合同意（core set agreement）需要 Ω(L·n^{2+1/d}) 比特。这些异步下界对发送遗漏（send-omission）对手成立，且即使协议使用密码学也无法避免。其核心论据是：如果某个法定人数（quorum）的非故障方达成一致输出并终止，那么他们在终止前发送的消息必须足以让法定人数之外的方也能以相同输出终止。令人惊讶的是，如果不需要参与者在输出后停止发送消息，则这些下界不再成立。作者设计了一个非终止的容忍遗漏的可靠广播协议，可针对任意参数 δ>1 调整，通信成本为 (1 + 1/(δ-1))·L·n + O(δ·n^2·log(δ·n)) 比特，这一结果本身具有独立意义。最后，作者展示了如何在满足 Q^d 条件下以 O(L·n^{1+1/d} + n^2·log n) 比特实现终止，从而证明异步下界是紧的。本文为一般对手结构下的共识协议通信复杂度提供了重要的理论界限，对分布式系统安全性设计具有指导意义。