pith. sign in

arxiv: 2606.31657 · v1 · pith:O3QPCZY3new · submitted 2026-06-30 · 💻 cs.DS

Sensitivity Lower Bounds via Locally Testable Codes

Yuichi Yoshida , Zihan Zhang This is my paper

Pith reviewed 2026-07-01 02:51 UTC · model grok-4.3

classification 💻 cs.DS
keywords sensitivitylocally testable codesapproximation algorithmsMax E3LIN2Max Cutconstraint satisfactionnon-signaling modelstability
0
0 comments X

The pith

Any near-optimal algorithm for satisfiable Max E3LIN2 must change its output on Ω(n) input positions after a single bit flip.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a general method that converts any locally testable code into a lower bound on the sensitivity of approximation algorithms for the CSP encoded by that code. When the method is instantiated with the c³-LTC, it produces a constant ε > 0 such that every (1-ε)-approximation algorithm for satisfiable Max E3LIN2 instances has sensitivity Ω(n). The same method, combined with standard reductions, yields sensitivity lower bounds for near-optimal algorithms on maximum clique and maximum k-coverage. A separate instantiation with a repetition code shows that (1-ε)-approximation algorithms for Max Cut on bipartite graphs must have sensitivity Ω(1/ε) whenever ε is O(1/√n). These bounds are used to derive averaged sensitivity statements and locality lower bounds in the non-signaling model.

Core claim

A general scheme turns any locally testable code into a sensitivity lower bound for the CSP encoded by the code; instantiating the scheme with the c³-LTC produces a constant ε > 0 such that every (1-ε)-approximation algorithm for satisfiable Max E3LIN2 has sensitivity Ω(n), and the same scheme applied to a repetition code produces an Ω(1/ε) sensitivity lower bound for (1-ε)-approximations of Max Cut on bipartite graphs when ε = O(1/√n).

What carries the argument

The general scheme that converts any locally testable code into a sensitivity lower bound for the encoded CSP.

If this is right

  • Every (1-ε)-approximation algorithm for satisfiable Max E3LIN2 has sensitivity Ω(n) for some fixed ε > 0.
  • Standard reductions produce an n^{1-O(ε)} sensitivity lower bound for n^{-ε}-approximation algorithms for maximum clique.
  • Standard reductions produce an Ω(k) sensitivity lower bound for (1-ε)-approximation algorithms for maximum k-coverage.
  • Any (1-ε)-approximation algorithm for Max Cut on bipartite graphs has sensitivity Ω(1/ε) whenever ε = O(1/√n).
  • The sensitivity bounds imply both averaged sensitivity lower bounds for randomized algorithms and locality lower bounds in the non-signaling model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same conversion scheme could be applied to other locally testable codes to obtain sensitivity lower bounds for additional CSPs.
  • The results indicate that requiring stability on top of approximation quality forces algorithms into regimes already ruled out by the trivial upper bounds.
  • The non-signaling locality lower bounds may extend to other models that generalize the LOCAL model once the sensitivity connection is fixed.

Load-bearing premise

The general scheme that converts any locally testable code into a sensitivity lower bound for the encoded CSP must hold with the stated quantitative parameters.

What would settle it

A (1-ε)-approximation algorithm for satisfiable Max E3LIN2 whose output changes on o(n) positions after any single input bit flip would falsify the Ω(n) claim.

read the original abstract

Sensitivity quantifies how far an algorithm's output can move in Hamming distance when a single input element is perturbed. We present a general scheme turning any locally testable code (LTC) into a sensitivity lower bound for the CSP encoded by the code. Instantiating it with the $c^3$-LTC yields a constant $\varepsilon > 0$ for which every $(1-\varepsilon)$-approximation algorithm for satisfiable Max E3LIN2 has sensitivity $\Omega(n)$, strengthening the previous $\Omega(n^\delta)$ lower bound known only for general instances. Standard reductions give an $n^{1-O(\varepsilon)}$ lower bound for $n^{-\varepsilon}$-approximation algorithms for maximum clique, and an $\Omega(k)$ bound for $(1-\varepsilon)$-approximation algorithms for maximum $k$-coverage, among others. These lower bounds match trivial upper bounds and imply that even slightly stable algorithms cannot achieve these approximations. A second instantiation, using a simple repetition code, shows that any $(1-\varepsilon)$-approximation algorithm for Max Cut on bipartite graphs has sensitivity $\Omega(1/\varepsilon)$ as long as $\varepsilon = O(1/\sqrt{n})$, extending the prior result for exact algorithms (the regime $\varepsilon < 1/n$). Thus even on bipartite graphs, where a perfect cut always exists, near-optimal solutions cannot be maintained stably. Our sensitivity lower bounds have two applications. First, they yield averaged sensitivity lower bounds, implying that any nearly optimal randomized algorithm for Max E3SAT has linearly many output bits that, after fixing the random seed, are Boolean functions with large influence. Second, via the sensitivity-to-locality connection, they imply locality lower bounds in the non-signaling model, which generalizes $\mathsf{LOCAL}$ and quantum-$\mathsf{LOCAL}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript presents a general scheme converting any locally testable code into a sensitivity lower bound for the CSP it encodes. Instantiating with the c³-LTC yields a constant ε > 0 such that every (1-ε)-approximation algorithm for satisfiable Max E3LIN2 has sensitivity Ω(n), strengthening the prior Ω(n^δ) bound. Reductions extend this to n^{1-O(ε)} sensitivity for n^{-ε}-approximations to maximum clique and Ω(k) for (1-ε)-approximations to maximum k-coverage. A repetition-code instantiation gives Ω(1/ε) sensitivity for (1-ε)-approximations to Max Cut on bipartite graphs when ε = O(1/√n). Applications include averaged sensitivity lower bounds for Max E3SAT and locality lower bounds in the non-signaling model.

Significance. If the reduction and parameter tracking hold, the results strengthen sensitivity lower bounds to match trivial upper bounds in several settings, implying that even slightly stable algorithms cannot achieve the stated approximations on satisfiable instances. The explicit mapping from LTC parameters (soundness, queries, distance) to sensitivity is a methodological contribution, and the applications to averaged sensitivity and non-signaling locality follow directly from the core bounds.

major comments (1)
  1. [§3] §3: The general LTC-to-sensitivity reduction must be checked to confirm that the quantitative mapping from constant soundness gap, constant query complexity, and constant relative distance of the c³-LTC produces a constant ε > 0 and Ω(n) sensitivity (rather than a weaker n^δ term) for the encoded Max E3LIN2 instances.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive recommendation of minor revision and for highlighting the need to verify the parameter mapping in the core reduction. We address the single major comment below.

read point-by-point responses

  1. Referee: [§3] §3: The general LTC-to-sensitivity reduction must be checked to confirm that the quantitative mapping from constant soundness gap, constant query complexity, and constant relative distance of the c³-LTC produces a constant ε > 0 and Ω(n) sensitivity (rather than a weaker n^δ term) for the encoded Max E3LIN2 instances.

    Authors: Section 3 presents the general reduction with explicit dependence on the LTC parameters (soundness gap σ > 0, query complexity q = O(1), relative distance ρ = Ω(1)). Substituting the constants from the c³-LTC (which are all independent of n) directly yields ε = Θ(σ/q) = Ω(1) and sensitivity Ω(ρ n) = Ω(n). The earlier Ω(n^δ) bound arose from LTCs whose soundness or distance degraded with n; the c³-LTC avoids this degradation, so the linear bound follows immediately from the same formulas. The proof of Theorem 3.1 already performs this substitution; we are happy to add a short remark after the theorem statement explicitly plugging in the c³-LTC constants if the referee finds the current presentation insufficiently explicit. revision: partial

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper defines a general reduction from any LTC (with tracked parameters for soundness, queries, and distance) to a sensitivity lower bound on the encoded CSP; this reduction is derived explicitly in Section 3 and does not presuppose the target sensitivity quantities. Instantiation with the external c³-LTC construction and the trivial repetition code then produces the stated Ω(n) and Ω(1/ε) bounds by direct substitution of known constants, without fitting, renaming, or load-bearing self-citation. Standard CSP reductions to clique and k-coverage are likewise external. The derivation is therefore self-contained against external benchmarks and receives score 0.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only. The central claims rest on the existence and quantitative properties of c³-LTCs and on standard reductions between CSPs; no free parameters or invented entities are visible.

axioms (1)
  • domain assumption Existence of c³-LTCs with the required density and testability parameters
    Invoked when instantiating the general scheme to obtain the Ω(n) sensitivity bound for Max E3LIN2.

pith-pipeline@v0.9.1-grok · 5857 in / 1316 out tokens · 48541 ms · 2026-07-01T02:51:32.043467+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

50 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    Akbari, X

    A. Akbari, X. Coiteux-Roy, F. d’Amore, F. Le Gall, H. Lievonen, D. Melnyk, A. Modanese, S. Pai, M.-O. Renou, V. Rozhoˇ n, and J. Suomela. Online locality meets distributed quantum computing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1295–1306, 2025

    2025

  2. [2]

    Arfaoui and P

    H. Arfaoui and P. Fraigniaud. What can be computed without communications? ACM SIGACT News, 45(3):82–104, 2014

    2014

  3. [3]

    Barak and K

    B. Barak and K. Marwaha. Classical algorithms and quantum limitations for maximum cut on high-girth graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS) , pages 14–1, 2022

    2022

  4. [4]

    Barto, A

    L. Barto, A. Krokhin, and R. Willard. Polymorphisms, and how to use them, 2017

    2017

  5. [5]

    R. B. Boppana. The average sensitivity of bounded-depth circuits. Information Processing Letters, 63(5):257–261, 1997

    1997

  6. [6]

    Bourtoule, V

    L. Bourtoule, V. Chandrasekaran, C. A. Choquette-Choo, H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pages 141–159, 2021

    2021

  7. [7]

    Bresler and B

    G. Bresler and B. Huang. The algorithmic phase transition of random k-SAT for low degree polynomials. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 298–309. IEEE, 2021

    2021

  8. [8]

    A. A. Bulatov and M. A. Valeriote. Recent results on the algebraic approach to the CSP. In Complexity of Constraints: An Overview of Current Research Themes , pages 68–92. Springer, 2008

    2008

  9. [9]

    Censor-Hillel, R

    K. Censor-Hillel, R. Levy, and H. Shachnai. Fast distributed approximation for max-cut. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS) , pages 41–56, 2017

    2017

  10. [10]

    W.-K. Chen, D. Gamarnik, D. Panchenko, and M. Rahman. Suboptimality of local algorithms for a class of max-cut problems. The Annals of Probability , 47(3):1587–1618, 2019

    2019

  11. [11]

    Coiteux-Roy, F

    X. Coiteux-Roy, F. d’Amore, R. Gajjala, F. Kuhn, F. Le Gall, H. Lievonen, A. Modanese, M.- O. Renou, G. Schmid, and J. Suomela. No distributed quantum advantage for approximate graph coloring. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1901–1910, 2024. 31

    1901

  12. [12]

    Dinur, S

    I. Dinur, S. Evra, R. Livne, A. Lubotzky, and S. Mozes. Locally testable codes with constant rate, distance, and locality. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages 357–374, 2022

    2022

  13. [13]

    Dong and N

    D. Dong and N. Mani. Random local access for sampling k-sat solutions. CoRR, abs/2409.03951, 2024

    work page arXiv 2024

  14. [14]

    Feige, S

    U. Feige, S. Goldwasser, L. Lov´ asz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM , 43(2):268–292, 1996

    1996

  15. [15]

    Fleming and Y

    N. Fleming and Y. Yoshida. Sensitivity lower bounds for approximation algorithms. In Pro- ceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2026. to appear

    2026

  16. [16]

    Friedgut

    E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Com- binatorica, 18(1):27–35, 1998

    1998

  17. [17]

    Gamarnik

    D. Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences , 118(41):e2108492118, 2021

    2021

  18. [18]

    Gamarnik, E

    D. Gamarnik, E. Mossel, and I. Zadik. Sharp thresholds imply circuit lower bounds: from random 2-SAT to planted clique. CoRR, abs/2311.04204, 2023

    work page arXiv 2023

  19. [19]

    Gamarnik and M

    D. Gamarnik and M. Sudan. Limits of local algorithms over sparse random graphs. In Pro- ceedings of the 5th conference on Innovations in theoretical computer science , pages 369–376, 2014

    2014

  20. [20]

    Gavoille, A

    C. Gavoille, A. Kosowski, and M. Markiewicz. What can be observed locally? round-based models for quantum distributed computing. In International Symposium on Distributed Com- puting (DISC), pages 243–257, 2009

    2009

  21. [21]

    Goldreich, T

    O. Goldreich, T. Gur, and I. Komargodski. Strong locally testable codes with relaxed local decoders. ACM Transactions on Computation Theory , 11(3):1–38, 2019

    2019

  22. [22]

    Goldreich and M

    O. Goldreich and M. Sudan. Locally testable codes and PCPs of almost-linear length. Journal of the ACM , 53(4):558–655, 2006

    2006

  23. [23]

    G¨ o¨ os, P

    M. G¨ o¨ os, P. Kamath, R. Robere, and D. Sokolov. Adventures in monotone complexity and TFNP. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 38:1–38:19. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2019

    2019

  24. [24]

    C. Guo, T. Goldstein, A. Hannun, and L. van der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, pages 3832–3842. PMLR, 2020

    2020

  25. [25]

    Hara and Y

    S. Hara and Y. Yoshida. Average sensitivity of decision tree learning. In The 11th International Conference on Learning Representations (ICLR), 2023

    2023

  26. [26]

    Hassidim, J

    A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak. Local graph partitions for approxi- mation and testing. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 22–31, 2009. 32

    2009

  27. [27]

    H˚ astad

    J. H˚ astad. Some optimal inapproximability results.Journal of the ACM , 48(4):798–859, 2001

    2001

  28. [28]

    H. Hatami. A structure theorem for boolean functions with small total influences. Annals of Mathematics, 176(1):509–533, 2012

    2012

  29. [29]

    A. E. Holroyd, O. Schramm, and D. B. Wilson. Finitary coloring. The Annals of Probability , pages 2867–2898, 2017

    2017

  30. [30]

    S. Khot, G. Kindler, E. Mossel, and R. O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing , 37(1):319–357, 2007

    2007

  31. [31]

    Kumabe and Y

    S. Kumabe and Y. Yoshida. Average sensitivity of dynamic programming. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1925–1961, 2022

    1925

  32. [32]

    Kumabe and Y

    S. Kumabe and Y. Yoshida. Average sensitivity of the knapsack problem. In 30th Annual European Symposium on Algorithms (ESA) , pages 75–1, 2022

    2022

  33. [33]

    Kumar, C

    A. Kumar, C. Seshadhri, and A. Stolman. Random walks and forbidden minors III: poly(dε−1)- time partition oracles for minor-free graph classes. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 257–268, 2022

    2022

  34. [34]

    S. Li, W. He, R. Bai, and P. Peng. Average sensitivity of hierarchical k-median clustering. In Forty-second International Conference on Machine Learning , 2025

    2025

  35. [35]

    N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing , 21(1):193– 201, 1992

    1992

  36. [36]

    Marwaha and S

    K. Marwaha and S. Hadfield. Bounds on approximating Max k XOR with quantum and classical local algorithms. Quantum, 6:757, 2022

    2022

  37. [37]

    T. T. Nguyen, T. T. Huynh, Z. Ren, P. L. Nguyen, A. W.-C. Liew, H. Yin, and Q. V. H. Nguyen. A survey of machine unlearning. ACM Transactions on Intelligent Systems and Technology, 16(5):1–46, 2025

    2025

  38. [38]

    Panteleev and G

    P. Panteleev and G. Kalachev. Asymptotically good quantum and locally testable classical LDPC codes. In Proceedings of the 54th annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 375–388, 2022

    2022

  39. [39]

    Peng and Y

    P. Peng and Y. Yoshida. Average sensitivity of spectral clustering. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD) , pages 1132–1140, 2020

    2020

  40. [40]

    J. Pich. Circuit lower bounds in bounded arithmetics. Annals of Pure and Applied Logic , 166(1):29–45, 2015

    2015

  41. [41]

    B. Rossman. The average sensitivity of bounded-depth formulas. Computational Complexity, 27(2):209–223, 2018

    2018

  42. [42]

    Fast Local Computation Algorithms

    R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. Fast local computation algorithms. CoRR, abs/1104.1377, 2011

    work page internal anchor Pith review Pith/arXiv arXiv 2011

  43. [43]

    Srinivasan and A

    S. Srinivasan and A. Thangaraj. Codes on planar tanner graphs. Advances in Mathematics of Communications, 6(2):131–163, 2012. 33

    2012

  44. [44]

    Trevisan, G

    L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing , 29(6):2074–2097, 2000

    2074

  45. [45]

    Varma and Y

    N. Varma and Y. Yoshida. Average sensitivity of graph algorithms. SIAM Journal on Com- puting, 52(4):1039–1081, 2023

    2023

  46. [46]

    Yoshida and S

    Y. Yoshida and S. Ito. Average sensitivity of Euclidean k-clustering. Advances in Neural Information Processing Systems, 35:32487–32498, 2022

    2022

  47. [47]

    Yoshida and Z

    Y. Yoshida and Z. Zhang. Low-sensitivity matching via sampling from Gibbs distributions. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2026

    2026

  48. [48]

    Yoshida and S

    Y. Yoshida and S. Zhou. Sensitivity analysis of the maximum matching problem. In 12th Innovations in Theoretical Computer Science Conference (ITCS) , pages 58–1, 2021. A Proof of Lemma 2.5 It suffices to exhibit an encoder f whose image is C and whose message coordinates appear in fixed positions after a permutation of coordinates. Since C is linear, C = ...

    2021

  49. [49]

    ˜f(Fk p) = fM Fk p = ΠC

  50. [50]

    Thus ˜f is a systematic encoder for the permuted code Π C, witnessing that Π C is systematic with the same parameters

    The first k coordinates of ˜f(m) equal P ˜f(m) = PfM(PfM)−1m = m. Thus ˜f is a systematic encoder for the permuted code Π C, witnessing that Π C is systematic with the same parameters. Undoing the permutation shows that C becomes systematic after the fixed coordinate permutation Π, as claimed. 34