Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Sensitivity Lower Bounds for Approximation Algorithms

Fleming, Noah LU orcid and Yoshida, Yuichi (2026) 37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026 p.4043-4076
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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
editor
Larsen, Kasper Green and Saha, Barna
pages
34 pages
publisher
Association for Computing Machinery
conference name
37th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026
conference location
Vancouver, Canada
conference dates
2026-01-11 - 2026-01-14
external identifiers
  • scopus:105033622428
ISBN
9781611978971
DOI
10.1137/1.9781611978971.149
language
English
LU publication?
yes
id
7d152ab5-2616-4353-857a-d724165d308d
date added to LUP
2026-05-13 13:34:34
date last changed
2026-05-13 13:35:39
@inproceedings{7d152ab5-2616-4353-857a-d724165d308d,
  abstract     = {{<p>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.</p>}},
  author       = {{Fleming, Noah and Yoshida, Yuichi}},
  booktitle    = {{Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026}},
  editor       = {{Larsen, Kasper Green and Saha, Barna}},
  isbn         = {{9781611978971}},
  language     = {{eng}},
  pages        = {{4043--4076}},
  publisher    = {{Association for Computing Machinery}},
  title        = {{Sensitivity Lower Bounds for Approximation Algorithms}},
  url          = {{http://dx.doi.org/10.1137/1.9781611978971.149}},
  doi          = {{10.1137/1.9781611978971.149}},
  year         = {{2026}},
}