In computational complexity theory, sensitivity quantifies how much an algorithm's output can change in Hamming distance when a single input is perturbed. We present a general scheme that transforms any Locally Testable Code (LTC) into a sensitivity lower bound for the corresponding Constraint Satisfaction Problem (CSP).
By instantiating it with the $c^3$-LTC, we derive a constant $\theta_0$ such that every $(1-\theta)$-approximation algorithm for satisfiable Max E3LIN2 has sensitivity $\Omega(n)$, strengthening the previous $\Omega(n^\theta)$ lower bound known only for general instances.
Standard reductions yield an $n^{1-O(\theta)}$ lower bound for $n^{-\theta}$-approximation algorithms for maximum clique, and an $\Omega(k)$ bound for $(1-\theta)$-approximation algorithms for maximum $k$-coverage, among others. These lower bounds match trivial upper bounds, indicating that even slightly stable algorithms cannot achieve these approximations.
A second instantiation, using a simple repetition code, shows that any $(1-\theta)$-approximation algorithm for Max Cut on bipartite graphs has sensitivity $\Omega(1/\theta)$ as long as $\theta = O(1/\sqrt{n})$, extending the prior result for exact algorithms (in the regime where $\theta$ approaches 0).
Blogger's Review: This paper offers a fresh perspective on sensitivity lower bounds through Locally Testable Codes, revealing the limitations of algorithm output stability in constraint satisfaction problems. Notably, the instantiation with $c^3$-LTC not only strengthens existing lower bounds but also provides a crucial reference framework for future research, emphasizing the complexity and constraints in algorithm design. These results are significant for understanding and constructing effective approximation algorithms.