我们研究近似算法的敏感度，即在单个输入修改下输出分布的变化幅度。结果表明，对于集合覆盖、支配集、Min‑Rep 以及最小无权有向 3‑spanner，即使只要求 $\log^{\beta} n$ 的近似，也必须拥有 $n^{\Omega(1)}$ 的敏感度，其中 $\beta>0$ 为常数，$n$ 为集合规模或图的顶点数。该下界同样适用于任意随机算法，计算资源不受限制。 在有界度图上，这些敏感度下界直接转化为随机 LOCAL 模型以及其非信号化推广中的对数局部性下界。对于支配集，固定 $\varepsilon\in(0,1)$ 并取足够大的最大度 $\Delta$，$(1+\varepsilon)\ln\Delta$ 的近似可以在敏感度和 LOCAL 轮数上独立于 $n$。然而将比率提升至 $(1-\varepsilon)\ln\Delta$ 则需要 $n^{\Omega_{\varepsilon,\Delta}(1)}$ 的敏感度，进而得到 $\Omega_{\varepsilon,\Delta}(\log n)$ 的局部性下界。最小无权有向 3‑spanner 的任意常数近似也必须在有向无环图（最大总度常数）上拥有对数局部性。 核心技术是对低噪声标签覆盖（low‑soundness Label Cover）变体的多项式敏感度下界。Fleming 与 Yoshida 已经证明在可满足实例需要几乎全部约束满足时的下界，我们将其扩展到逆多项式对数比例的满足率，从而支撑上述归约。具体做法是改写 Impagliazzo‑Kabanets‑Wigderson 的直接乘积构造并结合 Dinur‑Harsha 的迭代组合，以控制输入编辑的传播，并设计在标签和源实例同时变化时仍保持稳定的恢复过程。 点评：本文首次将敏感度与局部性统一起来，给出一系列经典图论问题在近似质量与局部通信复杂度之间的严格权衡，为后续在分布式和随机近似算法中探索更细粒度的下界提供了有力工具。