We study the sensitivity of approximation algorithms, i.e., how much their output distribution changes after a single input edit. We prove that for Set Cover, Dominating Set, Min‑Rep and the minimum unweighted directed 3‑spanner, even a $\log^{\beta} n$ approximation forces sensitivity $n^{\Omega(1)}$, where $\beta>0$ is an absolute constant and $n$ denotes the universe size or the number of vertices. The lower bounds hold for any randomized algorithm with unrestricted computation. On bounded‑degree graphs, these sensitivity lower bounds translate directly into logarithmic locality lower bounds in the randomized LOCAL model and its non‑signaling extension. For Dominating Set, fixing $\varepsilon\in(0,1)$ and choosing a sufficiently large maximum degree $\Delta$, a $(1+\varepsilon)\ln\Delta$ approximation can be achieved with sensitivity and LOCAL round complexity independent of $n$. Improving the ratio to $(1-\varepsilon)\ln\Delta$ requires sensitivity $n^{\Omega_{\varepsilon,\Delta}(1)}$, yielding a locality lower bound of $\Omega_{\varepsilon,\Delta}(\log n)$. Any constant‑factor approximation for the minimum unweighted directed 3‑spanner also demands logarithmic locality, even on DAGs with constant maximum total degree. The key ingredient is a polynomial sensitivity lower bound for a variant of low‑soundness Label Cover. Fleming and Yoshida established such a bound when the required fraction of satisfied constraints on satisfiable instances is close to one. We extend this to inverse‑polylogarithmic fractions, enabling the reductions above. Technically we adapt the Impagliazzo‑Kabanets‑Wigderson direct‑product construction together with the Dinur‑Harsha iterated composition to control the propagation of input edits, and we design recovery procedures that remain stable when both the supplied labeling and the source instance change. Review: This work unifies sensitivity and locality, delivering tight trade‑offs between approximation quality and local communication complexity for several classic graph problems, and provides powerful tools for future investigations of fine‑grained lower bounds in distributed and randomized approximation algorithms.