arXiv:2604.02582 · v2

Sensitivity and Locality Lower Bounds via Low-Soundness Label Cover

首次提交 2026-04-03 07:35

版本更新 2026-11-06 04:20

雷达观测 2026-11-09 10:16

摘要

We study the sensitivity of approximation algorithms, which measures how much their output distributions change under a single input edit. We show that, for Set Cover, Dominating Set, Min-Rep, and minimum unweighted directed 3-spanner, even a $\log^βn$ approximation requires sensitivity $n^{Ω(1)}$, for some absolute constant $β>0$ and all sufficiently large $n$. The lower bounds hold even for randomized algorithms with unrestricted computation. Here $n$ is the universe size for Set Cover and the number of vertices for the graph problems. On bounded-degree graphs, our sensitivity lower bounds imply logarithmic locality lower bounds in the randomized LOCAL model and its non-signaling generalization. For Dominating Set, fix $\varepsilon\in(0,1)$ and a sufficiently large constant maximum-degree bound $Δ$. A $(1+\varepsilon)\lnΔ$ approximation can be achieved with sensitivity and LOCAL round complexity independent of $n$. We show that improving the ratio to $(1-\varepsilon)\lnΔ$ requires sensitivity $n^{Ω_{\varepsilon,Δ}(1)}$, and hence locality $Ω_{\varepsilon,Δ}(\log n)$. For minimum unweighted directed 3-spanner, every constant approximation factor requires logarithmic locality, even on DAGs of 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 lower 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 to the problems above. We adapt the Impagliazzo--Kabanets--Wigderson direct-product construction and Dinur--Harsha iterated composition to control the propagation of input edits, and design recovery procedures that are stable under changes to both the supplied labeling and the source instance.