Sensitivity Lower Bounds for Approximaiton Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915556284694528 |
|---|---|
| author | Fleming, Noah Yoshida, Yuichi |
| author_facet | Fleming, Noah Yoshida, Yuichi |
| contents | 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 LOCAL, quantum-LOCAL, and bounded dependence models, we establish locality lower bounds for several graph problems in the non-signaling model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02744 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sensitivity Lower Bounds for Approximaiton Algorithms Fleming, Noah Yoshida, Yuichi Data Structures and Algorithms Computational Complexity 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 LOCAL, quantum-LOCAL, and bounded dependence models, we establish locality lower bounds for several graph problems in the non-signaling model. |
| title | Sensitivity Lower Bounds for Approximaiton Algorithms |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2411.02744 |