💻 computer science

Sensitivity Lower Bounds via Locally Testable Codes

This paper establishes a general framework converting locally testable codes into sensitivity lower bounds for approximation algorithms, demonstrating that even slightly stable algorithms cannot achieve near-optimal solutions for problems like Max E3LIN2, Max Cut on bipartite graphs, and Maximum Clique, thereby yielding new averaged sensitivity and non-signaling locality lower bounds.

Original authors: Yuichi Yoshida, Zihan Zhang

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuichi Yoshida, Zihan Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a very busy, high-stakes kitchen. You have a master recipe book (the algorithm) that tells you how to prepare a meal based on a list of ingredients (the input).

Sensitivity is a measure of how much your final dish changes if you accidentally swap out just one single ingredient.

Low Sensitivity: You swap a pinch of salt for a pinch of pepper, and the dish tastes almost exactly the same. The recipe is "stable."
High Sensitivity: You swap that one pinch of salt, and suddenly the entire dish becomes a completely different meal. The recipe is "unstable."

This paper asks a fundamental question: Is it possible to have a recipe that is both "nearly perfect" (very close to the best possible meal) AND "stable" (doesn't change much if you tweak one ingredient)?

The authors say: No. In fact, for many complex problems, if you want a nearly perfect result, you are forced to have a recipe that is wildly unstable. Changing one tiny thing in the input forces you to completely rewrite the output.

Here is how they proved it, using some clever metaphors:

1. The "Secret Code" Analogy (Locally Testable Codes)

The authors use a mathematical tool called a Locally Testable Code (LTC). Think of this as a secret language used by spies.

The Message: A secret note.
The Code: The note is written in a special, redundant way. Even if a spy changes a few letters, the code can detect the error.
The Test: A guard can check if a message is real by looking at just a few letters (like checking the first, middle, and last word). If the message is fake, the guard will catch it with high probability.

The authors realized that these secret codes are mathematically identical to complex puzzle games (called Constraint Satisfaction Problems).

The Puzzle: You have to fill in a grid of numbers so that every row and column adds up correctly.
The Connection: If you try to solve this puzzle "almost perfectly" (getting 99% of the rows right), the math of the secret code forces you to be extremely sensitive. If you change just one clue in the puzzle, your "almost perfect" solution has to change drastically to stay valid.

2. The "Bipartite Graph" (The Perfect Split)

One of their most surprising findings involves Max Cut on Bipartite Graphs.

The Metaphor: Imagine a party with two groups of people (Group A and Group B). Everyone in Group A only knows people in Group B, and vice versa. You want to split the room into two sides so that the maximum number of friendships cross the divide.
The Good News: In this specific setup, a "perfect" split always exists. It's easy to find the perfect solution.
The Bad News: The authors proved that even though the perfect solution is easy, any algorithm trying to find a solution that is almost perfect (99% good) is incredibly fragile. If you remove just one friendship (one edge), the algorithm might have to move half the people to the other side of the room to maintain its "almost perfect" score.

They showed that the more perfect you try to be (the closer to 100%), the more unstable the algorithm becomes. If you demand 99.9% perfection, a tiny change in the input causes a massive change in the output.

3. The "Covering" Problem

They also looked at a problem called Maximum k-Coverage.

The Metaphor: You have a giant map of a city and a set of 100 different bus routes. You want to pick 5 routes that cover the most neighborhoods.
The Finding: Even if you only need to cover 99% of the city, if you remove just one neighborhood from the map, your list of 5 bus routes might have to change completely. You can't just swap one bus for another; you might have to pick a totally different set of 5 buses.

4. What This Means for Computers (The "Brain" Analogy)

The paper also translates these findings into the language of computer circuits (the "brain" of the algorithm).

They proved that for these hard problems, the "brain" of any algorithm that finds a near-perfect solution must be deep and complex.
It cannot be a simple, shallow circuit (like a quick glance). It has to be a deep, tangled web of logic.
The "Influence" Concept: They showed that the output of these algorithms depends on many different parts of the input. If you change one input bit, it ripples through the whole system. You can't isolate the effect.

Summary of the "Takeaway"

The paper essentially says: Stability and Near-Perfection are enemies.

If you are trying to solve a complex optimization problem (like scheduling, routing, or packing) and you demand a solution that is very close to the best possible one, you cannot rely on a "stable" algorithm. The moment the real world changes slightly (a data point shifts, a connection breaks), your "near-perfect" solution will likely collapse and require a total reconstruction.

This isn't just a theoretical curiosity; it sets a hard limit on how robust our AI and optimization tools can ever be. If you want the best results, you must accept that your system will be highly sensitive to tiny changes.

Technical Summary: Sensitivity Lower Bounds via Locally Testable Codes

Problem Statement
The paper investigates the sensitivity of algorithms for combinatorial optimization problems. Sensitivity quantifies the maximum change in an algorithm's output (measured in Hamming distance for deterministic algorithms, or Earth Mover's Distance for randomized algorithms) when a single input element is perturbed (e.g., a constraint is deleted or an edge is removed). While low-sensitivity algorithms exist for various problems, establishing tight lower bounds has been challenging. Previous work by Fleming and Yoshida established $\Omega(n^\delta)$ lower bounds for approximation algorithms of canonical Constraint Satisfaction Problems (CSPs) like Max E3SAT, Max E3LIN2, and Max Cut, but these bounds were not tight (exponentially far from the trivial $O(n)$ upper bound) and relied on reductions that obscured the behavior on satisfiable instances.

Methodology
The authors propose a general framework that converts the properties of Locally Testable Codes (LTCs) into sensitivity lower bounds for the CSPs encoded by those codes.

LTC-Induced CSPs: The authors consider a systematic linear LTC $C$ with block length $n$ , message length $k$ , relative distance $\delta$ , rate $r$ , and detection probability $\kappa$ . They construct a CSP instance where the input variables correspond to the non-message coordinates of the codeword, and the constraints correspond to the local tests performed by the LTC tester. If the input message is $m$ , the instance is satisfiable by the codeword $f(m)$ .
Approximation as Encoding: A $(1-\epsilon)$ -approximation algorithm for this CSP is viewed as an "approximate encoder." If the algorithm achieves a high satisfaction ratio, the strong testability property of the LTC ensures that the algorithm's output is close (in Hamming distance) to a valid codeword.
Nearest-Message Decoder: The authors introduce a nearest-message decoder $\sigma$ that maps a near-optimal assignment back to the closest message $m$ . They analyze the distribution of $\sigma$ applied to the algorithm's output.
Symmetrization and Total Variation Gap: To derive a lower bound, the authors define a functional $L$ representing the average Earth Mover's Distance (EMD) between the outputs of the algorithm on neighboring messages $m$ and $m'$ . By symmetrizing the algorithm's output distribution over permutations of message coordinates and alphabet symbols, they prove that the total variation distance between the decoded messages for neighboring inputs must be large.
Triangle Inequality Argument: Finally, they relate the distance between outputs on neighboring messages to the sensitivity of the algorithm. Since neighboring messages differ in only one coordinate, the corresponding CSP instances differ by a constant number of constraints (bounded by the variable degree $\theta$ of the LTC tester). By applying the triangle inequality along the chain of constraint deletions, they convert the average distance bound into a worst-case sensitivity lower bound.

Key Contributions and Results

The paper instantiates this framework with two specific families of LTCs to derive new, tight sensitivity lower bounds:

Max E3LIN2 and Max E3SAT (via c3-LTCs):
- Using the $c_3$ -LTCs (based on Left-Right Cayley Complexes) which have constant rate, distance, and detection probability, the authors prove that any $(1-\epsilon)$ -approximation algorithm for Max E3LIN2 on satisfiable instances must have sensitivity $\Omega(n)$ .
- This result matches the trivial upper bound of $n$ , strengthening the previous $\Omega(n^\delta)$ bound.
- Via standard reductions, this implies an $\Omega(n)$ sensitivity lower bound for $(1-\epsilon)$ -approximation algorithms for Max E3SAT and Max Cut on general graphs, even on satisfiable instances.
Max Cut on Bipartite Graphs (via Repetition Codes):
- The authors construct a specific LTC based on signed repetition codes and bipartite expanders. The associated CSP is exactly Max Cut on bipartite graphs.
- They prove that for any $(1-\epsilon)$ -approximation algorithm on bipartite graphs (where a perfect cut always exists), the sensitivity is $\Omega(1/\epsilon)$ for $\epsilon = O(1/\sqrt{n})$ .
- This extends previous results known only for exact algorithms ( $\epsilon < 1/n$ ) to the regime of near-optimal approximations, showing that even on highly structured bipartite graphs, near-optimal solutions cannot be maintained stably.
Maximum Clique and Maximum $k$ -Coverage:
- Applying reductions from Max E3LIN2, the authors derive an $n^{1-O(\epsilon)}$ sensitivity lower bound for the Maximum Clique problem. This improves upon the previous $\Omega(n^\delta)$ bound and matches the performance of a naive truncation strategy.
- For the Maximum $k$ -Coverage problem, they show that any $(1-\epsilon)$ -approximation algorithm has sensitivity $\Omega(k)$ , even when a solution covering all elements exists. This matches the trivial upper bound of $k$ .
Boolean-Function Consequences:
- The instability results are translated into the language of Boolean functions. The authors show that for any randomized algorithm producing near-satisfying assignments for a specific family of satisfiable Max E3SAT formulas, the output bits (when the random seed is fixed) must have large influence.
- Specifically, linearly many output bits have influence $\Omega(k)$ , implying they are far from small juntas and pseudo-juntas, have linear decision-tree depth, and cannot be computed by polynomial-size constant-depth circuits (randomized $\mathsf{AC}^0$ ).
Locality Lower Bounds in the Non-Signaling Model:
- Leveraging the connection between sensitivity and locality, the authors derive lower bounds for the non-signaling model (which generalizes classical LOCAL and quantum-LOCAL models).
- They show that achieving $(1-\epsilon)$ -approximations for satisfiable Max E3LIN2 requires locality $\Omega(\log n)$ , and for bipartite Max Cut requires locality $\Omega(\log(1/\epsilon))$ .

Significance
The paper claims that these results are significant for several reasons:

Tightness: The lower bounds match the trivial upper bounds for several problems (Max E3LIN2, Max $k$ -Coverage), proving that even slightly stable algorithms cannot achieve these approximations.
Satisfiable Instances: Unlike previous PCP-based reductions which often required unsatisfiable or "hard" instances, these bounds hold even for satisfiable instances where optimal solutions are known to exist.
Generality: The framework unifies the analysis of sensitivity across different problems (CSPs, Clique, Coverage) and models (randomized algorithms, non-signaling distributions).
Structural Barriers: The Boolean-function consequences provide a new perspective on the limitations of low-depth circuits and local algorithms for satisfiable optimization problems, ruling out efficient approximations even when the algorithm is allowed to output any near-optimal assignment.

The work establishes that the existence of Locally Testable Codes inherently imposes a fundamental barrier to the stability of approximation algorithms for the problems they encode.