Sensitivity Lower Bounds for Approximation Algorithms
Noah Fleming, Yuichi Yoshida · 2024
Read Sensitivity Lower Bounds for Approximation Algorithms by Noah Fleming, Yuichi Yoshida (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-02744.txt.
Description
Abstract Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitivity have been developed for many problems, no sensitivity lower bounds were previously known for approximation algorithms.
Catalog record
| CREATOR | Noah Fleming, Yuichi Yoshida |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-02744
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Sensitivity Lower Bounds for Approximation Algorithms Noah Fleming, Yuichi Yoshida Abstract Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitivity have been developed for many problems, no sensitivity lower bounds were previously known for approximation algorithms. In this work, we establish the first polynomial lower bound on the sensitivity of (randomized) approximation algorithms for constraint satisfaction problems (CSPs) by adapting the probabilistically checkable proof (PCP) framework to preserve sensitivity lower bounds. From this, we derive polynomial sensitivity lower bounds for approximation algorithms for a variety of problems, including maximum clique, minimum vertex cover, and maximum cut. Leveraging the connection between sensitivity and locality in the non-signaling model, which subsumes the 𝖫𝖮𝖢𝖠𝖫 \mathsf{LOCAL} , quantum- 𝖫𝖮𝖢𝖠𝖫 \mathsf{LOCAL} , and bounded dependence models, we establish locality lower bounds for several graph problems in the non-signaling model. Contents 1 Introduction The notion of algorithmic sensitivity, introduced by Varma and Yoshida [ VY23 ] , measures the stability of an algorithm’s output in Hamming distance (or the earth mover’s distance if the algorithm is randomized) when an element in the input is added or deleted. In practical situations, low sensitivity is desirable because inputs can easily change due to noise or over time. If an algorithm has high sensitivity, it may lose reproducibility, erode user trust, and lead to inconsistent decisions. Since this concept was introduced, low-sensitivity algorithms have been developed for many graph problems. Some representative results include a 2 -approximation algorithm for the minimum vertex cover problem with sensitivity O(1) [ CHHK16 , VY23 ] , a (1-\varepsilon) -approximation algorithm for the maximum matching problem with sensitivity \Delta^{O(1/\varepsilon)} [ YZ26 ] , where \Delta is the maximum degree, an additive O(n^{2/3}) -approximation algorithm for the minimum s - t cut problem with sensitivity O(n^{2/3}) , where the output is a vertex set [ VY23 ] , and a (1+\varepsilon) -approximation algorithm for the shortest path problem with sensitivity O(\varepsilon^{-1}\log^{3}n) (with respect to edge contractions instead of additions or deletions) [ KY23 ] . Moreover, it has been shown that algorithms with low sensitivity can be used to design online algorithms with small recourse [ YI22 ] , as well as online learning algorithms with low regret [ DY24 ] . Therefore, it is important to understand whether low sensitivity algorithms can be achieved for each problem. On the lower bound side, the only known general result that we are aware of is that any randomized algorithm for finding a proper 2 -coloring of a bipartite graph with n vertices requires sensitivity \Omega(n) [ VY23 ] , which follows easily from the fact that a connected bipartite graph has only two proper 2 -colorings such that the Hamming distance between them is \Omega(n) . Indeed, there are no known lower bounds on the sensitivity of approximation algorithms, leaving a significant gap in our knowledge. This is especially true, since all of the known upper bounds are derived from approximation algorithms. 1.1 Our Contributions 1.1.1 Sensitivity Lower Bounds In this work, we show polynomial sensitivity lower bounds for (even randomized) approximation algorithms for various combinatorial problems by adapting the probabilistically checkable proofs (PCP) framework [ ALM+98 , AS98 ] . We emphasize that this is the first time that lower bounds for approximation algorithms have been established. We are able to derive lower bounds for a variety of combinatorial problems through reductions, and we present some representative results next. We start with the maximum clique problem. Consider a (potentially inefficient) n^{-\varepsilon} -approximation algorithm that outputs a clique of size at most n^{1-\varepsilon} . Its sensitivity is trivially bounded by O(n^{1-\varepsilon}) and this is the only known upper bound. We show that the polynomial dependency on n is necessary: Theorem 1.1 . There are universal constants \varepsilon,\delta>0 such that any (inefficient) algorithm for the maximum clique problem that outputs an n^{-\varepsilon} -approximate clique with probability 1-O(1/n) has sensitivity \Omega(n^{\delta}) . We note that the lower bound also applies to the maximum independent set problem. Additionally, our proof is information-theoretic, and the lower bounds presented in this work apply even to inefficient algorithms. Next, we consider the minimum vertex cover problem. As we mentioned, there exists a 2 -approximation algorithm for the minimum vertex cover problem with sensitivity O(1) [ CHHK16 , VY23 ] . We prove that the sensitivity must increase significantly as the approximation ratio approaches one. Theorem 1.2 . There are universal constants \varepsilon,\delta>0 such that any (randomized and inefficient) (1+\varepsilon) -approximation algorithm for the minimum vertex cover problem has sensitivity \Omega(n^{\delta}) . Finally, we discuss the maximum cut problem, where the output is a vertex set. Trivially, the random assignment algorithm is a 1/2 -approximation algorithm with sensitivity zero, and we can obtain an (inefficient) additive \widetilde{O}(\sqrt{\varepsilon^{-1}nm}) -approximation algorithm with sensitivity O(\varepsilon n) by converting a differentially private algorithm [ EKKL20 ] . As mentioned, the only known lower bound is that exact algorithms, which can solve 2 -coloring, must have sensitivity \Omega(n) [ VY23 ] . We show that the sensitivity must remain polynomial as the approximation ratio approaches one: Theorem 1.3 . There exist universal constants \varepsilon,\delta>0 such that any (randomized and inefficient) (1-\varepsilon) -approximation algorithm for the maximum cut problem has sensitivity \Omega(n^{\delta}) . We can obtain similar lower bounds for other constraint satisfaction problems (CSPs) including \mathsf{E3SAT} and \mathsf{3LIN} . 1.1.2 Locality Lower Bounds for the Non-Signaling Model Although the notion of sensitivity is interesting in its own right, it has a close connection to the non-signaling model [ ACRd+25 , CRdG+24 ] , also known as the \varphi - \mathsf{LOCAL} model and the causal model [ AF14 , GKM09 ] . In this model, given a graph G=(V,E) , we can produce an arbitrary output distribution as long as it does not violate the non-signaling principle: for any set of vertices S\subseteq V , modifying the structure of the input graph at more than a distance t from S does not affect the output distribution of S . The parameter t is called the locality of the model. It is stronger than any “physical” synchronous distributed computing model, and in particular, the non-signaling model is more powerful than the \mathsf{LOCAL} model for distributed algorithms on graphs [ Lin92 ] , the quantum- \mathsf{LOCAL} model [ GKM09 ] , and the bounded dependence model [ HSW17 ] , all with the same locality [ ACRd+25 ] . Suppose that we can generate a distribution in the non-signaling model for a graph problem with locality t . Then, an algorithm that samples from this distribution and outputs the result has sensitivity O(\Delta^{t}) , where \Delta is the maximum degree of the graph, since deleting an edge affects the marginal distributions of at most \Delta^{t} vertices. Building on this connection, we can extend various lower bounds that were only known for the \mathsf{LOCAL} model to the non-signaling model, including an \Omega(1/\varepsilon) lower bound for an n^{-\varepsilon} -approximation algorithm for the maximum independent set problem [ BHKK16 ] , an \Omega(\log n) lower bound for a (1+\varepsilon) -approximation algorithm for the minimum vertex cover problem for some constant \varepsilon>0 [ GS14 ,