在计算复杂性理论中，敏感度衡量了当单个输入元素发生扰动时，算法输出在汉明距离上的最大移动距离。我们提出了一种通用方案，将任何局部可测试编码（LTC）转化为对应于编码的约束满足问题（CSP）的敏感度下界。
通过$c^3$-LTC的实例化，我们得到了一个常数$\theta_0$，对于每个$(1-\theta)$-近似算法在可满足的Max E3LIN2问题上，其敏感度为$\Omega(n)$，这加强了之前仅针对一般实例的$\Omega(n^\theta)$下界。
标准的归约方法给出了$n^{1-O(\theta)}$的下界，适用于最大团问题的$n^{-\theta}$-近似算法，以及对于最大$k$-覆盖问题的$\Omega(k)$下界。这些下界与简单的上界相匹配，表明即使是稍微稳定的算法也无法达成这些近似值。
第二个实例化，使用简单的重复编码，表明任何$(1-\theta)$-近似算法在二分图上的Max Cut问题中，其敏感度为$\Omega(1/\theta)$，只要$\theta = O(1/\sqrt{n})$，这扩展了先前针对精确算法的结果（$\theta$趋近于0的情况）。
博主点评： 本文通过局部可测试编码提供了敏感度下界的新视角，揭示了在约束满足问题中算法输出的稳定性限制。特别是，利用$c^3$-LTC的实例化不仅强化了现有的下界，还为后续研究提供了重要的参考框架，展示了算法设计中的复杂性与限制。值得关注的是，这些结果对于理解和构造有效的近似算法具有重要意义。