1 Introduction↩︎

The (worst-case) sensitivity of an algorithm is the maximum change in its output, measured in Hamming distance, when a single input element is perturbed. For randomized algorithms we compare output distributions using earth mover’s distance (EMD). Sensitivity offers a foundational robustness metric for algorithms and has deep connections to sublinear-time and distributed computation [1]. Sensitivity also underpins consistent decision making and reproducible knowledge discovery. Prior work has developed low-sensitivity algorithms for numerous combinatorial optimization problems [2]–[6], clustering tasks [7]–[9], and decision tree learning [10].

On the lower-bound side, it is known that computing \(2\)-coloring of a bipartite graph requires sensitivity \(\Omega(n)\) [2]. Recently, Fleming and Yoshida [1] leveraged probabilistically checkable proofs (PCPs) to show that, for canonical constraint satisfaction problems (CSPs) such as Max E3SAT, Max E3LIN2, and Max Cut, there exist constants \(\varepsilon, \delta > 0\) for which any \((1-\varepsilon)\)-approximation algorithm must have sensitivity \(\Omega(n^\delta)\), where \(n\) denotes the number of variables or vertices. Standard reductions then yield \(\Omega(n^\delta)\) lower bounds for approximation algorithms for the maximum clique and minimum vertex cover problems. While their framework provides the first nontrivial lower bounds for approximation algorithms, it nevertheless has several shortcomings:

• The \(\Omega(n^\delta)\) sensitivity bound is evidently far from tight.

• The lower bounds for Max E3LIN2 and Max Cut are obtained via gadget reductions from Max E3SAT, so they say nothing about approximation algorithms for satisfiable instances.

• The argument applies only to worst-case sensitivity, leaving the behavior under randomly chosen perturbations unresolved.

In this work we address these shortcomings by relating sensitivity to locally testable codes (LTCs) and showing how the existence of an LTC yields sensitivity lower bounds. We outline the framework below.

1.1 Our Contributions↩︎

1.1.0.1 Sensitivity Lower Bounds for CSPs via LTCs.

Locally testable codes (LTCs) [11] are error-correcting codes whose membership can be checked by probing only a constant number of coordinates of the received word. An LTC is called a strong LTC [12] if there exists \(\kappa > 0\) such that the rejection probability is at least \(\kappa\) times the relative distance from the code. The parameter \(\kappa\) is called the detection probability of the code. As we only consider strong LTCs in this work, we also call them LTCs. In this work, we mainly consider linear codes, meaning they form a subspace of \(\mathbb{F}_p^n\).

An LTC naturally induces a CSP instance: we regard each coordinate of the input word as a variable, and each test performed by the tester as a constraint on those variables. The variable degree \(\theta\) of the tester is the maximum number of constraints that query any single coordinate. If the input is a codeword the instance is satisfiable, whereas inputs far from the code violate a fraction of the constraints that is proportional to their distance from the code. For an LTC \(C\), let \(\mathsf{MaxCSP}(C)\) denote the Max CSP whose constraints are restricted to those used in the tester for \(C\). Throughout the introduction, we measure sensitivity for CSP instances with respect to deleting a single constraint. The main contribution of this work is showing a general scheme that converts a linear LTC \(C\) to a sensitivity lower bound of \(\mathsf{MaxCSP}(C)\).

We emphasize that this lower bound is information-theoretic and does not rely on any complexity assumption.

We first instantiate 1 using the \(c^3\)-LTC of [13], [14], which enjoys constant relative distance, constant rate, a constant number of queries, and constant detection probability. The associated CSP is Max E3LIN2, whose constraints are linear equations of the form \(x + y + z = b\) over \(\mathbb{F}_2\).

Since the assignment length is \(n\), every algorithm automatically has sensitivity at most \(n\), so 2 matches this trivial upper bound up to the hidden constant. Equivalently, for satisfiable Max E3LIN2, even slightly stable algorithms cannot achieve a \((1-\varepsilon)\)-approximation.

Previously, the best lower bound was \(\Omega(n^\delta)\) for some \(\delta > 0\), and it applied only to arbitrary (not necessarily satisfiable) instances [1]. This non-tight exponent comes from the PCP-based reduction: it blows an \(n\)-variable instance up to size about \(N := n^{1/\delta}\), so even if the \(\Omega(n)\) sensitivity lower bound survives the reduction, expressing the result in terms of the enlarged instance size \(N\) leaves only an \(\Omega(N^\delta)\) lower bound.

Via standard reductions from Max E3LIN2 to Max 3SAT and Max Cut (see, e.g., [15]), we can show that \((1-\varepsilon)\)-approximation algorithms for Max E3SAT must have sensitivity \(\Omega(n)\) even on satisfiable instances, and that \((1-\varepsilon)\)-approximation algorithms for Max Cut on general graphs incur sensitivity \(\Omega(n)\) as well. These results again improve upon the prior sensitivity bound of \(\Omega(n^\delta)\) [1].

To derive a sensitivity bound specific to Max Cut on bipartite graphs, we construct an LTC whose associated CSP is precisely Max Cut and substitute it into 1. The result is striking because it holds even on bipartite inputs, where a perfect cut always exists:

Thus even on this highly structured class, where the optimum cut is trivial, any near-optimal algorithm must make \(\Omega(1/\varepsilon)\) changes after a single edge deletion. As we mentioned, it was known that any algorithm for \(2\)-coloring a bipartite graph requires \(\Omega(n)\) sensitivity [2], which matches the regime \(\varepsilon < 1/n\) in 3. Our result generalizes this by showing an \(\Omega(1/\varepsilon)\) sensitivity bound for all \(\varepsilon\) as large as \(\Theta(1/\sqrt{n})\).

1.1.0.2 Sensitivity Lower Bounds for Other Combinatorial Problems.

Applying the standard FGLSS reduction [16] together with the serial repetition to 2, as in [1], yields the following lower bound for the maximum clique problem. Here, we consider the setting that the algorithm outputs a vertex set that forms a clique, and sensitivity is measured with respect to deleting a single edge.

Consider the naive (and inefficient) strategy that computes the maximum clique and then truncates it to size at most \(n^{1-\varepsilon}\). This procedure achieves an \(n^{-\varepsilon}\) approximation with sensitivity \(n^{1-\varepsilon}\), and 4 shows that this dependence is essentially optimal. Also, the previous lower bound [1] shows that there exist some constants \(\varepsilon,\delta>0\) such that any \(n^{-\varepsilon}\)-approximation algorithm has sensitivity \(\Omega(n^\delta)\). By contrast, our lower bound of \(\Omega(n^{1-c\varepsilon})\) holds for any \(\varepsilon > 0\).

We also study the maximum \(k\)-coverage problem, where an instance consists of a universe \(U\) and a family \(\mathcal{F}\) of subsets of \(U\). The goal is to select a subfamily \(\mathcal{S} \subseteq \mathcal{F}\) of \(k\) sets that covers as many elements as possible. Sensitivity is measured with respect to deleting a single element from \(U\) (and removing it from every set in \(\mathcal{F}\)). Via a reduction from Max E3SAT we derive the following:

Observe that any algorithm for the maximum \(k\)-coverage problem has sensitivity at most \(k\), since its output contains at most \(k\) sets. Thus 5 shows that even permitting a slight approximation does not improve over this trivial upper bound. We also note that, combining the prior \(\Omega(n^\delta)\) lower bound for Max E3SAT [1] with the same reduction yields only \(\Omega(k / n^{1-\delta})\), which is negligible. Achieving a linear lower bound is therefore essential.

1.1.0.3 Boolean-Function Consequences.

The LTC construction behind 2 also gives a Boolean-function barrier for satisfiable Max E3SAT. Under the standard reduction, each message \(m \in \{0,1\}^k\) indexes a formula \(\Phi(m)\) in an explicit satisfiable family, and flipping one message bit changes only \(O(1)\) clauses. Composing a randomized approximation algorithm with the map \(m \mapsto \Phi(m)\) and then fixing its internal randomness turns each output bit into a Boolean function on \(\{0,1\}^k\). The influence of an output bit is the expected number of message coordinates whose flip changes that bit, equivalently, the expected number of adjacent formulas \(\Phi(m)\) and \(\Phi(m^{\oplus i})\) on which that output bit differs. Our sensitivity lower bound therefore implies that, averaged over the internal randomness, linearly many output coordinates have influence \(\Omega(k)\):

Friedgut’s junta theorem and Hatami’s pseudo-junta theorem [17], [18] show that small total influence forces strong structural simplification. Our theorem therefore implies that linearly many output bits stay a constant distance away from all small juntas and pseudo-juntas (5). It also implies that linearly many output coordinates have linear decision-tree depth (6). Likewise, average-sensitivity bounds of Boppana and Rossman [19], [20] yield lower bounds for randomized polynomial-size constant-depth circuits (that is, randomized \(AC^0\)) and randomized bounded-depth formulas (7).

Unlike previous lower bounds for random \(k\)-SAT, including the bounded-depth decision lower bound of Gamarnik, Mossel, and Zadik and the low-degree-polynomial search lower bound of Bresler and Huang [21], [22], these lower bounds apply to an explicit satisfiable Max E3SAT family and rule out randomized \(AC^0\) circuits and bounded-depth formulas for producing near-satisfying assignments even when the algorithm may output any of many near-optimal assignments.

1.1.0.4 Locality Lower Bounds for the Non-signaling Model.

Our sensitivity bounds remain strong even in the non-signaling model, which strictly generalizes classical \(\mathsf{LOCAL}\), quantum-\(\mathsf{LOCAL}\), and bounded-dependence models: satisfiable Max E3LIN2 still requires locality \(\Omega(\log n)\), and bipartite Max Cut requires locality \(\Omega(\log(1/\varepsilon))\).

In the non-signaling model [23]–[26], 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. This model is stronger than any “physical” synchronous distributed computing model, and in particular, it contains classical \(\mathsf{LOCAL}\) [27], quantum-\(\mathsf{LOCAL}\) [26], and the bounded-dependence model [28]. Consequently, any locality lower bound in the non-signaling model applies automatically to these models.

The following observation from [1] connects locality to sensitivity. Suppose we generate a distribution in the non-signaling model for a graph problem with locality \(t\). Sampling from this distribution and outputting the result yields an algorithm whose sensitivity is \(O(\Delta^t)\), where \(\Delta\) denotes the maximum degree, because deleting an edge can affect the marginal distributions of at most \(\Delta^t\) vertices. Because the CSP instance produced by the \(c^3\)-LTC [13], [14] has constant degree, 2 translates into the following lower bound:

Marwaha and Hadfield [29] showed that achieving a \((1-\varepsilon)\)-approximation on satisfiable instances already requires \(\Omega(\log n)\) rounds in quantum-\(\mathsf{LOCAL}\), and Fleming and Yoshida [1] proved the same locality bound in the non-signaling model for general instances. Our theorem unifies these results by establishing that even satisfiable Max E3LIN2 instances demand \(\Omega(\log n)\) locality for non-signaling distributions.

Similarly, 3 yields the following lower bound for the non-signaling model:

Hence setting \(\varepsilon = n^{-\delta}\) for any small constant \(\delta > 0\) forces locality \(\Omega(\log n)\). The previously best locality barrier on bipartite graphs is that any one-round quantum-\(\mathsf{LOCAL}\) algorithm achieves at most a \((\frac{1}{2}+\frac{1}{\sqrt{2d}})\)-approximation on \(d\)-regular bipartite graphs [30]. No stronger locality lower bound was known that rules out \((1-\varepsilon)\)-approximations on bipartite inputs, even for \(\mathsf{LOCAL}\).

On general graphs, there exist \((1-\varepsilon)\)-approximation algorithms in \(\mathsf{LOCAL}\) (and even \(\mathsf{CONGEST}\)) that run in \(O(\mathrm{poly}(1/\varepsilon)\cdot \log n)\) rounds [31]. By contrast, Fleming and Yoshida [1] showed an \(\Omega(\log n)\) locality lower bound in the non-signaling model for achieving \((1-\varepsilon)\) approximation for some \(\varepsilon > 0\).

1.2 Proof Overview↩︎

We first sketch the argument underlying 1 and then outline how it yields [thm:e3lin2-intro,thm:max-cut-intro].

1.2.0.1 An analogy between optimization problems and systematic LTCs.

We exploit a tight parallel between optimization problems and systematic LTCs, where systematic means that the encoder copies the \(k\) message symbols verbatim into designated coordinates, inducing a canonical input/output split. We write \(x \sim x'\) for neighboring instances.

Consider an optimization problem with input space \(\mathcal{I}\), output space \(\mathcal{O}\), and evaluation map \(e : \mathcal{I} \times \mathcal{O} \to [0,1]\). A deterministic \((1-\varepsilon)\)-approximation algorithm \(\mathcal{A} : \mathcal{I} \to \mathcal{O}\) satisfies \(e(x,\mathcal{A}(x)) \in [1-\varepsilon,1]\) for every \(x\). Attaching the input to the output, \(\tilde{\mathcal{A}}(x) = (x,\mathcal{A}(x))\), yields the diagram \[\mathcal{I} \xrightarrow{\;\tilde{\mathcal{A}}\;} \mathcal{I} \times \mathcal{O} \xrightarrow{\;e\;} [1-\varepsilon,1].\] The sensitivity of \(\mathcal{A}\) is the maximum, over neighboring inputs \(x\sim x'\), of the distance between \(\tilde{\mathcal{A}}(x)\) and \(\tilde{\mathcal{A}}(x')\) inside \(\mathcal{I}\times\mathcal{O}\). To derive a lower bound we therefore search for neighboring inputs that force any \((1-\varepsilon)\)-approximation algorithm to output points that are well separated for at least two inputs in \(\mathcal{I}\times\mathcal{O}\), mirroring the coding-theoretic requirement that distinct messages map to distant codewords.

Now replace the algorithm by a systematic LTC \(C\) with an encoder \(f\). Let \(n\) be the block length, \(k\) be the message length, \(\delta\) be the relative distance, and \(T\) be the tester with detection probability \(\kappa\). Then, define \(e(x) = \ifthenelse{\isempty{}} {\mathbf{Pr}\left[T \text{ accepts } x\right]} {\mathop{\mathbf{Pr}}_{}\left[T \text{ accepts } x\right]}\). Every codeword \(f(m)\) for a message \(m\) satisfies \(e(m, f(m)) = 1\), so we obtain the analogous diagram \[\Sigma^k \xrightarrow{\;f\;} \Sigma^k \times \Sigma^{n-k} \xrightarrow{\;e\;} \left\{1\right\}.\] Because the code has relative distance \(\delta\), distinct messages map to codewords whose relative Hamming distance is at least \(\delta\), mirroring the separation requirement for optimization algorithms.

To reason about approximate outputs we invoke strong testability. Think of \(f\) as an exact algorithm that always attains the optimum \(1\) of \(e\). If another encoder \(\mathcal{B}\) satisfies \(e(m,\mathcal{B}(m)) \ge 1-\varepsilon\), strong testability guarantees that \(\tilde{\mathcal{B}}(m)\) lies within distance \(\varepsilon/\kappa\) of some codeword. Consequently we get the diagram \[\Sigma^k \xrightarrow{\;\tilde{\mathcal{B}}\;} \Sigma^k \times \Sigma^{n-k} \xrightarrow{\;e\;} [1-\varepsilon,1].\] The distance between the codewords of neighboring messages \(m\sim m'\) therefore forces a comparable separation between \(\tilde{\mathcal{B}}(m)\) and \(\tilde{\mathcal{B}}(m')\), yielding the desired sensitivity lower bound.

The systematic nature of the code is crucial: it embeds the message directly into the codeword, so the tester \(T\) enforces consistency between input and output rather than merely checking membership in the code.

1.2.0.2 Any approximate encoder has high sensitivity.

With this analogy in place we outline how to prove the sensitivity lower bound for approximation algorithms on the induced CSP, thereby establishing 1. Fix a randomized \((1-\varepsilon)\)-approximation algorithm \(\mathcal{A}\) for \(\mathsf{MaxCSP}(C)\). Given a message \(m\), we construct a CSP instance \(\mathcal{I}_C(m)\) that is satisfiable exactly by the codeword for \(m\), and strong testability ensures that the output of \(\tilde{\mathcal{A}}\) on \(\mathcal{I}_C(m)\) lies within Hamming distance \(\varepsilon/\kappa\) of that codeword. Hence we may view \(\tilde{\mathcal{A}}\) as an approximate encoder that attempts to extend \(m\). To force large sensitivity we must find neighboring messages \(m\sim m'\) whose outputs fall into balls centred at different codewords. To this end we introduce the nearest-message decoder \(\sigma:\Sigma^n \to \Sigma^k\) and show that for some \(m\sim m'\) the values \(\sigma\circ\tilde{\mathcal{A}}(\mathcal{I}_C(m))\) and \(\sigma\circ \tilde{\mathcal{A}}(\mathcal{I}_C(m'))\) differ with constant probability; by the code’s relative distance this forces \(\tilde{\mathcal{A}}(\mathcal{I}_C(m))\) and \(\tilde{\mathcal{A}}(\mathcal{I}_C(m'))\) to have large earth mover’s distance.

However, it is not enough to focus on a single pair \(m \sim m'\): the encoder \(\tilde{\mathcal{A}}\) might always output the codeword for \(m\), achieving zero sensitivity while staying nearly optimal for \(m\) and \(m'\). Instead we average over all such pairs. For any approximate encoder \(\tilde{\mathcal{A}}\) we define a functional \(L\) that averages the earth mover’s distance between \(\tilde{\mathcal{A}}(\mathcal{I}_C(m))\) and \(\tilde{\mathcal{A}}(\mathcal{I}_C(m'))\) across all \(m\sim m'\). This functional lower bounds the worst-case sensitivity and, more strongly, the average sensitivity under uniformly random constraint deletions.

The difficulty is that \(\mathcal{A}\) can otherwise be arbitrary. Yet \(L\) is convex, so we may symmetrize \(\tilde{\mathcal{A}}\) by averaging over permutations of message coordinates and alphabet symbols without increasing \(L\). Composing the symmetrized encoder \(\bar{\mathcal{A}}\) with the nearest-message decoder \(\sigma\) produces, for each message \(m\), a distribution \(\nu_m^*\) over \(\Sigma^k\) whose probabilities depend only on the Hamming distance to \(m\), making the analysis tractable. We then show that some neighboring pair \(m\sim m'\) forces \(\sigma\circ\bar{\mathcal{A}}(\mathcal{I}_C(m))\) and \(\sigma\circ\bar{\mathcal{A}}(\mathcal{I}_C(m'))\) to differ with constant probability, yielding the desired sensitivity lower bound.

1.2.0.3 Sensitivity lower bounds from explicit LTCs

Given the connection between sensitivity lower bounds and LTCs, we instantiate our framework with two explicit families. First, we adapt the left-right Cayley complex (LRCC) codes of Dinur, Evra, Livne, Lubotzky, and Mozes [13] into systematic LTCs whose induced CSP is Max E3LIN2. This transformation preserves their rate, distance, and detection probability, letting us transfer the \(c^3\)-LTC guarantees and derive \(\Omega(n)\) average-sensitivity lower bounds for every \((1-\varepsilon)\)-approximation algorithm, thereby proving 2.

Second, we analyze signed repetition codes that duplicate each message coordinate alongside its complement. We partition the coordinates into \(A\) (original copies) and \(B\) (flipped copies), embed a bipartite expander on \(A\cup B\), and use a two-query tester that checks random edges for disagreement, thereby realizing a Max Cut instance. The replication factor controls both the rate and distance, and feeding this construction into our framework establishes 3.

1.3 Related Work and Discussion↩︎

1.3.0.1 Max Cut.

It is natural to ask whether one can beat the sensitivity lower bound of 3 by applying 1 to a different two-query LTC. However, in such a tester, every constraint enforces that a pair of queried coordinates differs, so codewords correspond exactly to 2-colorings of the tester’s constraint graph. The number of codewords, and hence the rate, is dictated by the number of connected components, while the minimum distance is governed by the sizes of those components. Consequently, an LTC obtained this way cannot simultaneously achieve high rate and large distance, preventing stronger lower bounds via this route.

1.3.0.2 Lower Bounds for Other CSPs.

For a linear code \(C\), \(\mathsf{MaxCSP}(C)\) necessarily collapses to a system of linear equations. Attempts to extend our lower bounds via gadget reductions such as pp-definitions or pp-interpretations [32], [33] stall here: starting from linear equations one cannot reach target languages whose expressive power is incomparable with (or weaker than) linear systems, so reductions to templates like 2SAT or Horn-SAT are ruled out. Another idea is to replace LTCs with dictatorship tests from the PCP literature [34], [35], but it remains unclear whether such tests can be adapted to yield sensitivity lower bounds.

1.3.0.3 Machine Unlearning

(Exact) machine unlearning is often formalized by requiring that, after deleting a data item, the algorithm’s output matches the model one would obtain by retraining on the pruned dataset [36]–[38]. Viewed through this lens, our sensitivity lower bounds translate directly into recourse lower bounds for unlearning. In particular, 5 shows that for the maximum \(k\)-coverage problem—a canonical abstraction for summarization and selection tasks—the deletion of a single universe element forces any exact-unlearning mechanism that maintains a \((1-\varepsilon)\)-approximation to modify \(\Omega(k)\) members of the selected set family to match the retrained solution. Hence exact unlearning cannot rely on small, local “patches”: even a single deletion necessitates wholesale restructuring of the learned summary.

1.3.0.4 Sensitivity on Planar Graphs

The constraint graph of a 2CSP instance has one vertex per variable and an edge for each constraint connecting the variables it involves. Our results establish lower bounds for the class of constraint graphs induced by the LTCs we employ; for instance, the repetition code we use for Max Cut yields an expander constraint graph.

A natural question is whether algorithms with low (average) sensitivity exist for non-expanding graphs such as planar ones. When the planar graph also has bounded degree, the partition oracle [39], [40] gives a \((1-\varepsilon)\)-approximate Max Cut algorithm with average sensitivity \(\mathrm{poly}(1/\varepsilon)\) under vertex deletions. However, it remains unclear whether an analogous guarantee holds for general planar graphs, where the maximum degree may be unbounded. For the lower-bound side, an LTC whose Tanner graph is planar and has rate \(\geq 5/8\) must have distance \(O(1/n)\) [41]. Consequently, applying 1 to planar graphs would require LTCs of smaller rate.

1.3.0.5 Overlap Gap Property.

The overlap gap property (OGP) is a geometric/topological description of near-optimal solution spaces: in many random optimization problems, the set of \((1-\varepsilon)\)-optimal solutions splits into clusters whose pairwise overlaps avoid a nontrivial interval. OGP has emerged as a unifying explanation for barriers for local algorithms in high-dimensional random structures [42], [43] and is surveyed by Gamarnik, who frames it as a topological obstruction to optimization [44]. Classical OGP analyzes overlaps between near-optimal solutions on the same instance (or across randomly coupled instances), whereas our sensitivity framework compares outputs of algorithms on two almost-identical instances. At a high level the direction is similar: both aim to rule out stable/local algorithms, i.e., OGP via geometric gaps in the near-optimal solution space, and our results via explicit worst-case instances where tiny input perturbations force large output changes.

1.3.0.6 Circuit-complexity lower bounds for SAT and related search problems.

For unrestricted circuits, lower bounds for search-SAT are closely connected to lower bounds for decision-SAT: Pich proved implications between formalized search and decision lower-bound principles [45]. Because such general lower bounds remain out of reach, known assumption-free results mostly concern restricted models, on both the decision and the search side. On the decision side, Gamarnik, Mossel, and Zadik proved that depth-\(d\) bounded-depth circuits for random \(2\)-SAT near the satisfiability threshold require size \(\exp(n^{\Theta(1/d)})\) [21]. On the search side, Bresler and Huang showed that low-degree polynomial algorithms cannot find satisfying assignments for random \(k\)-SAT at clause densities of order \(2^k \log k / k\), excluding a broad family of algorithms, including local methods and several message-passing procedures [22]. In a different restricted model, Göös, Kamath, Robere, and Sokolov proved exponential monotone circuit lower bounds for a monotone variant of XOR-SAT [46]. By contrast, our results give a lower bound for randomized bounded-depth circuits and formulas for producing near-satisfying assignments on an explicit satisfiable Max E3SAT family, rather than an average-case decision lower bound for random formulas or a lower bound in a different restricted search model.

2 Preliminaries↩︎

For a positive integer \(n\), let \([n]\) denote the set \(\{1,2,\ldots,n\}\). For two strings \(x,y \in \Sigma^n\), we write \(x \sim y\) when they differ on exactly one coordinate. Also, we write \(d_{\mathrm H}(x,y) := \#\{i \in [n] : x_i \neq y_i\}\) for the (unnormalized) Hamming distance and \(\delta_{\mathrm H}(x,y):= d_{\mathrm H}(x,y)/n\) for its normalized/relative version. Note that we use the relative Hamming distance only in the context of error-correcting codes. To avoid tedious transforms between normalized Hamming distances with different denominators, we always use the block length \(n\) of the code as the denominator when dealing with codes.

2.1 Sensitivity↩︎

Let \((\Omega,d)\) be a finite metric space and let \(\mu,\nu\) be distributions over \(\Omega\). The earth mover’s distance between \(\mu\) and \(\nu\) is \[\mathsf{EMD}_d(\mu,\nu) := \inf_{\pi\in\Pi(\mu,\nu)} \sum_{x,y\in\Omega} d(x,y)\,\pi(x,y),\] where \(\Pi(\mu,\nu)\) denotes the set of all couplings of \(\mu\) and \(\nu\). When the metric is clear from context we write simply \(\mathsf{EMD}(\mu,\nu)\). If \(d\) is the discrete metric on \(\Omega\), i.e., \(d(x, y) = 1\) when \(x\neq y\) and \(0\) otherwise, then \(\mathsf{EMD}_d(\mu,\nu) = \mathsf{TV}(\mu,\nu)\), the total variation distance between \(\mu\) and \(\nu\).

Consider a problem in which an input instance \(I\) consists of elements \(e_1,\ldots,e_n\) and the output space is a metric space \((\Omega,d)\). For an element \(e \in I\), let \(I - e\) denote the instance obtained by deleting \(e\). The sensitivity of a (possibly randomized) algorithm \(\mathcal{A}\) at \(I\) is \[\begin{align} \mathsf{Sens}(\mathcal{A},I) &:= \max_{i \in [n]} \mathsf{EMD}_d(\mathcal{A}(I), \mathcal{A}(I-e_i)), \end{align}\] where we identify \(\mathcal{A}(I)\) with its output distribution.

2.2 Locally Testable Codes↩︎

For \(w\in\Sigma^n\) and a subset \(C\subseteq \Sigma^n\), we set \(\delta_{\mathrm H}(w, C) := \min_{c\in C} \delta_{\mathrm H}(w, c)\).

The next lemma shows that any linear locally testable code becomes systematic after permuting coordinates. The proof is deferred to 7.

2.3 Constraint Satisfaction Problems↩︎

Let \(V\) be a finite set of variables and let \(\Sigma\) be a finite alphabet. An instance of a constraint satisfaction problem (CSP) over \(\Sigma\) is a tuple \((V, \Sigma, \mathcal{C})\), where \(\mathcal{C}\) is a finite collection of constraints. Each constraint is given by a pair \((S, R)\) with \(S \subseteq V\) its scope and \(R \subseteq \Sigma^{S}\) the set of allowed local assignments. An assignment \(\alpha \in \Sigma^{V}\) satisfies \((S, R)\) if \(\alpha|_{S} \in R\), and it is a solution to the instance when it satisfies every constraint in \(\mathcal{C}\). The associated maximum constraint satisfaction problem (Max CSP) asks for an assignment \(\alpha \in \Sigma^{V}\) that maximizes the number of satisfied constraints.

For a CSP instance \(\mathcal{I} = (V, \Sigma, \mathcal{C})\) and a constraint \(c\in \mathcal{C}\), we write \(\mathcal{I} - c\) for the instance obtained by removing \(c\) from \(\mathcal{C}\).

3 Sensitivity Lower Bounds via LTCs↩︎

The goal of this section is to prove 1. We organize the argument in four stages. First, 3.1 shows how a systematic LTC induces a CSP whose constraints mirror the tester. Next, in 3.2 we discuss the nearest-message decoder, which recovers the planted message from near-optimal assignments, and accompanying stability bounds. Building on these tools, 3.3 symmetrizes the decoder’s output distributions and proves a large total-variation gap between neighboring messages. Finally, 3.4 converts this gap into an earth mover’s distance lower bound for worst-case sensitivity, and the same argument also yields an average-sensitivity analogue, giving 1.

3.1 CSP Induced by an LTC↩︎

For \(m \in \Sigma^k\) and a subset \(U \subseteq \Sigma^{n-k}\), we write \(m \oplus U := \{(m, u) : u \in U\} \subseteq \Sigma^{n}\).

Intuitively, the message coordinates of a systematic codeword are fixed once we choose \(m\), so the only freedom left is the parity part. The tester’s local view on \(S\) allows exactly the projections of valid codewords onto \(S\). Intersecting \(V_S\) with \(m \oplus \Sigma^{n-k}\) therefore isolates those local patterns that agree with \(m\) on the message positions, and projecting them onto the parity indices \(S'\) yields the admissible assignments for the remaining variables. The family \(\mathcal{C}\) is just the collection of these derived local constraints, so any assignment to the parity coordinates satisfies the CSP instance precisely when it extends \(m\) to a full codeword in \(C\).

Notice that all constraints in \(\mathcal{I}_C(m)\) can be satisfied by assigning the code bits of \(f(m)\) to the variables.

Throughout this section we reuse the convention from the introduction: for any approximate algorithm \(\mathcal{A}\) for \(\mathsf{MaxCSP}(C)\) we define the randomized map \[\tilde{\mathcal{A}}(\mathcal{I}_C(m)) := (m, \mathcal{A}(\mathcal{I}_C(m)))\] which simply pairs the input message with the assignment returned by \(\mathcal{A}\).

3.2 Nearest-Message Decoder↩︎

We collect here the decoder and stability statements that connect near-optimal assignments to nearby codewords.

3.3 Total Variation Gap for Adjacent Messages↩︎

In this section, we consider symmetrizing the decoder’s output distributions for near-optimal assignments and show that the output distributions are well separated in total variation in expectation over neighboring messages.

Let \[\begin{align} &\mathcal{D}_\varepsilon :=\\ &\Bigl\{ (\nu_m)_{m\in\Sigma^k} \;\Big|\; \exists\,(1-\varepsilon)\text{-approx algorithm }\mathcal{A} \text{ for }\mathsf{MaxCSP}(C) \text{ with }\nu_m = \mathrm{law}(\sigma\circ \tilde{\mathcal{A}}(\mathcal{I}_C(m)))\text{ for all }m \Bigr\}. \end{align}\] Here \(\mathrm{law}(X)\) denotes the distribution of a random variable \(X\) and \(\sigma\) is the nearest-message decoder.

3.4 Worst-Case Sensitivity Bound↩︎

We now convert the total-variation gap into an earth-mover lower bound for neighboring messages.

4 Sensitivity Lower Bounds from Explicit LTCs↩︎

This section instantiates the abstract sensitivity framework developed in 3. We plug explicit families of locally testable codes into 1 to derive sensitivity lower bounds for Max E3LIN2 and Max Cut.

4.1 LRCC Codes and Max E3LIN2↩︎

In this section, we present our construction of a systematic LTC whose local tests are parity constraints on constantly many variables. Our construction is based on the left-right Cayley complex (LRCC) code introduced by [13], with the concrete construction as in Sections 5 and 6 in [13].

For completeness we recall the notation surrounding the left-right Cayley complex associated with the codes \(C_n\). Given such a code, let \(X\) denote its LRCC, a 2-dimensional simplicial complex. We write \(X(\ell)\) for the set of \(\ell\)-faces of \(X\), so \(X(0)\) is the set of vertices, \(X(1)\) the edges, and \(X(2)\) the 2-faces. For any vertex \(g\in X(0)\), the local view \(X_g \subseteq X(2)\) consists of the 2-faces that contain \(g\). The LRCC construction equips each local view \(X_g\) with a small code \(C_g\) obtained by restricting the global code to the coordinates indexed by \(X_g\). With this terminology in place, the local testability guarantee established in [13] can be stated as follows:

However, the local tests on \(X_g\) are systems of linear equations rather than single linear constraints, so we translate them into tests that query a constant number of variables.

Combining with 1, we immediately get the following.

4.2 Repetition Codes and Max Cut↩︎

Let \(t\) be even, \(A\sqcup B=[t]\) a fixed balanced partition with \(|A|=|B|=t/2\), and \(k\ge 1\). Over the alphabet \(\{0,1\}\) consider the signed \(t\)-fold repetition code \[\mathrm{Rep}^{\pm}(k,t) =\Bigl\{ y\in\{0,1\}^{tk}:\;\exists x\in\{0,1\}^k\;\text{s.t.}\; y_{a,i}=x_i\;\forall a\in A,\quad y_{b,i}=1-x_i\;\forall b\in B,\;\forall i\in[k]\Bigr\}.\] Fix any \(d\)-regular bipartite graph \(G=(A,B,E)\) on the vertex set \(A\cup B\) (\(|A|=|B|=t/2\)) and write \(\sigma(G)\in[0,1)\) for the second singular value of its normalized adjacency matrix (equivalently: the largest nontrivial absolute eigenvalue of the random-walk matrix on \(G\)). Consider the non-adaptive \(2\)-query tester \(T\) that, on input \(y\in\{0,1\}^{tk}\),

chooses \(i\in[k]\) uniformly at random, chooses a random edge \((a,b)\in E\), queries the two symbols \(y_{a,i},y_{b,i}\), and rejects iff \(y_{a,i}=y_{b,i}\).

The blocklength is \(n = tk\).

We use the following spectral Poincaré inequality for bipartite \(d\)-regular graphs.

Using any constant-degree bipartite expander family (e.g., Ramanujan graphs), \(\sigma(G)\le 2\sqrt{d-1}/d\), hence \(\kappa\ge 1-2\sqrt{d-1}/d\) is a positive constant.

5 Maximum \(k\)-Coverage↩︎

We show how the sensitivity lower bound for Max E3SAT implies a matching bound for the maximum \(k\)-coverage problem when algorithms achieve near-perfect coverage on perfectly coverable instances.

In the maximum \(k\)-coverage problem, an instance \(I = (U,\mathcal{F})\) has a universe \(U\) and a family \(\mathcal{F} \subseteq 2^{U}\). Outputs are \(k\)-subfamilies \(\mathcal{S} \subseteq \mathcal{F}\) encoded by their indicator vectors \(\mathbb{1}_{\mathcal{S}} \in \{0,1\}^{\mathcal{F}}\), and we measure distances with the Hamming metric \(d_{\mathrm H}(\mathbb{1}_{\mathcal{S}}, \mathbb{1}_{\mathcal{S}'}) = \left|\mathcal{S} \triangle \mathcal{S}'\right|\). Two instances are neighbors if they differ only in the incidence vector of a single element \(e \in U\): equivalently, we delete \(e\) and insert a fresh element whose membership across \(\mathcal{F}\) can be chosen arbitrarily.

5.1 Max E3SAT↩︎

In Max E3SAT, an instance \(\Phi = (V,\{0,1\},\mathcal{C})\) consists of variables \(V\) and 3-CNF clauses \(\mathcal{C} = \left\{C_1, \dots, C_m\right\}\). The output space is \(\{0,1\}^{V}\) equipped with the Hamming metric \(d_{\mathrm H}\). Combining the standard reduction from Max E3SAT to Max E3LIN2 with a swapping variant of [thm:main-intro,thm:e3lin2-intro] (obtained by adapting its proof to replace clause deletions with clause replacements) yields the following consequence.

5.2 Block Gadget Reduction↩︎

Fix integers \(n = \left|V\right|\) and \(k \le n\). Without loss of generality, we assume that \(n\) is divisible by \(k\). Partition \(V\) into \(k\) disjoint blocks \(V = V_1 \sqcup \cdots \sqcup V_k\) with \(\left|V_i\right| = n/k\). For each \(i \in [k]\) and \(\alpha \in \{0,1\}^{V_i}\) create a set \(S_{i,\alpha}\). For every clause \(C_j \in C\) create an element \(e_j\), and include \(e_j \in S_{i,\alpha}\) whenever the restriction \(\alpha\) satisfies a literal of \(C_j\) whose variable lies in \(V_i\). Let \(\mathcal{F} = \left\{S_{i,\alpha} \mid i \in [k], \alpha \in \{0,1\}^{V_i}\right\}\).

Let \(m = \left|C\right|\). Without loss of generality, we assume that \(m\) is divisible by \(k\). We choose \(M = m/k\). For each block \(i\), add a multiset \(G_i\) of \(M\) new guard elements. Every set \(S_{i,\alpha}\) contains the guards \(G_i\), while no set \(S_{i',\alpha'}\) with \(i' \neq i\) contains them. Write \(U_{\mathrm{cl}} = \left\{e_1, \dots, e_m\right\}\), \(U_{\mathrm{gd}} = \bigsqcup_{i=1}^k G_i\), and define \(U^+ = U_{\mathrm{cl}} \cup U_{\mathrm{gd}}\). The resulting maximum \(k\)-coverage problem instance is denoted by \(R_k^+(\Phi) = (U^+, \mathcal{F})\).

5.2.0.1 A canonical decoder.

Whenever \(\mathcal{S}\) contains exactly one set from each block we write it as \(\mathcal{S} = \left\{S_{i,\alpha_i}\right\}_{i=1}^k\) and define \(D(\mathcal{S}) \in \{0,1\}^{V}\) to be the concatenation of the block assignments.

5.3 Sensitivity Transfer↩︎

We now relate algorithms for the maximum \(k\)-coverage problem to algorithms for Max E3SAT.

6 A Boolean-Function View of Randomized Algorithms for Satisfiable Max E3SAT↩︎

In this section we recast the instability results from [sec:tv-distance,sec:sat] in the language of Boolean functions. We study randomized algorithms that, given a satisfiable Max E3SAT formula, output an assignment satisfying almost all clauses in expectation. Our hard instances are not arbitrary unrelated formulas: they form an explicit local subcube inside the ordinary SAT input space, indexed by messages \(m \in \{0,1\}^k\). All formulas in the family share the same variables and the same ordered clause skeleton, and flipping one bit of \(m\) changes only \(O(1)\) clause signs. Once the algorithm’s random seed is fixed, each output bit becomes an ordinary Boolean function of \(m\). Its influence is the sum, over all message coordinates, of the probability that flipping that coordinate changes the output bit. The main conclusion is that, on this explicit satisfiable family, these output bits cannot all have small influence: averaged over the random seed, the sum of their influences is necessarily large. This viewpoint is what later yields the junta, pseudo-junta, decision-tree, and bounded-depth circuit corollaries.

We say that a randomized algorithm \(A\) is one-sided \((1-\eta)\)-approximate for Max E3SAT if \(A\) is defined on every \(3\)-CNF formula and, for every satisfiable input formula \(\Phi\), \[\mathbb{E}_{a \sim A(\Phi)} \bigl[ \#\text{ clauses of }\Phi\text{ satisfied by }a \bigr] \ge (1-\eta)|\Phi|.\] Equivalently, if \(R\) denotes the internal random seed of \(A\), then \[\mathbb{E}_{R} \bigl[ \#\text{ clauses of }\Phi\text{ satisfied by }A(\Phi;R) \bigr] \ge (1-\eta)|\Phi|\] for every satisfiable \(\Phi\). No guarantee is required on unsatisfiable inputs. When \(A\) happens to be deterministic, the seed \(R\) is trivial and all of the statements below reduce to the deterministic version.

6.0.0.1 The standard formula encoding.

Fix integers \(n\) and \(M\), and regard a \(3\)-CNF formula on variable set \([n]\) with exactly \(M\) clauses as an ordered list \[\Phi = (C_1,\dots,C_M).\] Write each clause in the canonical order of its three variable indices, and encode each literal by the binary representation of its variable index in \([n]\) together with one sign bit indicating whether it is negated. Let \[\operatorname{Enc}_{n,M}(\Phi) \in \{0,1\}^{N}, \qquad N := M\bigl(3\lceil \log_2 n\rceil + 3\bigr),\] denote the concatenation of the \(M\) clause encodings. Throughout this section, when we write \(A(\Phi)\) for such a randomized algorithm \(A\), we mean the output distribution \(A(\operatorname{Enc}_{n,M}(\Phi))\) under this standard clause-by-clause encoding. Thus the ambient input space is the completely ordinary bit representation of \(3\)-CNF formulas; the parameter \(m \in \{0,1\}^k\) used below merely indexes an explicit hard subfamily inside that ambient space.

6.1 From Instability to Influence↩︎

We begin with the randomized E3LIN2 instability statement supplied by the LTC framework.

We now pass from E3LIN2 to E3SAT using the standard four-clause gadget. Because the E3LIN2 family already comes with a fixed ordered list of equation scopes, this step preserves a common template: varying \(m\) changes only the right-hand-side bits of \(O(1)\) equations, hence only the sign patterns in \(O(1)\) gadgets. For each equation \[x \oplus y \oplus z = b,\] let \(G_b(x,y,z)\) denote the standard \(4\)-clause gadget on the same variable triple with the property that any assignment satisfies all four clauses iff it satisfies the equation, and otherwise it satisfies exactly three clauses.

6.1.0.1 The hard embedding is itself simple.

Define the explicit input embedding \[x(m) := \operatorname{Enc}_{n,M}(\Phi(m)) \in \{0,1\}^{N}.\] Each output bit of \(x\) is either a fixed variable-index bit or a sign bit of a clause in one gadget, and the sign pattern of that gadget is determined by a single local E3LIN2 test. Since the tester query complexity is constant, each output bit of \(x\) depends on only \(O(1)\) message coordinates. Thus \(x\) is computable by a linear-size \(NC^0\) circuit. This is important for the randomized circuit corollary below: the hardness is not coming from a complicated front end, but from the randomized algorithm itself.

Because the relevant input family and output space are finite, any such randomized algorithm can be realized on a common finite probability space. We therefore fix a random seed \(R\) and a realization \(A(\cdot;R)\) whose law is \(A(\cdot)\) on every input. For the rest of the section write \[F_R(m) := A(x(m);R) = \bigl(f_{1,R}(m),\dots,f_{n,R}(m)\bigr) \in \{0,1\}^n.\] For each fixed seed \(r\) and output coordinate \(v\), the slice \(f_{v,r} : \{0,1\}^k \to \{0,1\}\) is an ordinary Boolean function. For a Boolean function \(f : \{0,1\}^k \to \{0,1\}\), write \[\operatorname{Inf}(f) := \sum_{i=1}^k \ifthenelse{\isempty{m \in \{0,1\}^k}} {\mathbf{Pr}\left[f(m)\neq f(m^{\oplus i})\right]} {\mathop{\mathbf{Pr}}_{m \in \{0,1\}^k}\left[f(m)\neq f(m^{\oplus i})\right]} .\] We call \[\operatorname{SCInf}(A) := \mathbb{E}_{R} \Bigl[ \sum_{v=1}^n \operatorname{Inf}(f_{v,R}) \Bigr]\] the seed-averaged cumulative influence of the pullback of \(A\) to the hard family. When \(A\) is deterministic, this is exactly the ordinary cumulative influence from the deterministic version of the section.

6.1.0.2 Why the pullback is the right object.

The theorem above is already stated in the standard formula-input model. We pass to the cube coordinates \(m \in \{0,1\}^k\) because the classical structural results we want to invoke, i.e., junta theorems, pseudo-junta theorems, and average-sensitivity upper bounds for bounded-depth circuits and formulas, are formulated for Boolean functions on product spaces. Moreover, by 13, adjacent points of the hard cube map to formulas whose standard encodings differ in only \(O(1)\) bits, so the pullback does not create artificial hardness: it is simply a convenient coordinate system for an explicit, genuinely local subfamily of ordinary SAT inputs. The role of the random seed is only to turn the randomized algorithm into deterministic slices to which these classical Boolean-function bounds apply.

6.2 A Meta-Corollary for Low-Influence Representation Classes↩︎

For a class \(\mathcal{G}_k\) of Boolean functions on \(\{0,1\}^k\), define \[\operatorname{dist}(f,\mathcal{G}_k) := \inf_{g \in \mathcal{G}_k} \ifthenelse{\isempty{m \in \{0,1\}^k}} {\mathbf{Pr}\left[f(m)\neq g(m)\right]} {\mathop{\mathbf{Pr}}_{m \in \{0,1\}^k}\left[f(m)\neq g(m)\right]} .\]

The strength of 4 is that it turns 2 into a black-box lower-bound principle:any coordinatewise representation class whose seedwise realizations have sublinear total influence is automatically ruled out on linearly many output coordinates on average over the seed. The next three subsections record concrete instantiations.

6.3 Anti-Junta and Anti-Pseudo-Junta Consequences↩︎

Recall that a Boolean function on \(\{0,1\}^k\) is a \(K\)-junta if it depends on at most \(K\) input coordinates. We also use Hatami’s notion of a \(K\)-pseudo-junta [18], which generalizes juntas by allowing the relevant coordinates to vary with the input in a structured way. We will not need the full formal definition here; the only property used below is that every \(K\)-pseudo-junta has total influence at most \(2K\).

The point of 5 is that the randomized task of finding near-satisfying assignments for an explicit satisfiable Max E3SAT family forces averaged non-junta structure: linearly many output coordinates stay a constant distance away from every small junta and every small pseudo-junta on average over the internal randomness.

6.4 Decision Trees and Local Dependence↩︎

For a Boolean function \(f : \{0,1\}^k \to \{0,1\}\), let \(D(f)\) denote its deterministic decision-tree depth, that is, the minimum worst-case number of input bits that must be queried in order to determine \(f(m)\).

What is new here is an explicit satisfiable bounded-occurrence family for which, even allowing internal randomness and approximation in expectation, linearly many seedwise output bits have linear deterministic query complexity with respect to the message coordinates, on average over the seed. This contrasts with local-access results that achieve polylogarithmic query complexity under strong LLL-type sparsity assumptions or in the high-\(k\)/low-degree regime [47], [48].

6.5 Constant-Depth Circuits and Formulas↩︎

We now record a bounded-depth consequence. Boppana’s average-sensitivity bound for constant-depth circuits and Rossman’s strengthening for bounded-depth formulas place polynomial-size bounded-depth computation in the low-influence regime on the message cube [19], [20]. Since our hard family is embedded into the standard SAT encoding by a linear-size \(NC^0\) map, the same barrier transfers to randomized bounded-depth computation for finding near-satisfying assignments on satisfiable Max E3SAT instances.

The point of 7 is that the obstruction already appears for randomized generation of near-satisfying assignments on satisfiable SAT formulas. Even though each satisfiable instance has many acceptable nearly optimal assignments and the algorithm may use internal randomness, the seedwise output bits still accumulate linear total influence on the hard family, and this rules out the usual polynomial-size bounded-depth circuit and formula classes.

7 Proof of 1↩︎

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 = M\mathbb{F}_p^k\) for some \(M\in \mathbb{F}_p^{n\times k}\) of rank \(k\). By the definition of rank, there exists a set of indices \(I=\{i_1, i_2,\dots,i_k\}\subseteq [n]\) such that the rows of \(M\) indexed by \(I\) span \(\mathbb{F}_p^k\). Let \(\Pi\in\mathbb{F}_p^{n\times n}\) be the permutation matrix that moves the coordinates in \(I\) to the first \(k\) positions and let \(\widetilde{M} := \Pi M\). The first \(k\) rows of \(\widetilde{M}\) span \(\mathbb{F}_p^k\), so the projection matrix \(P\in\mathbb{F}_p^{k \times n}\) onto those rows satisfies that \(P\widetilde{M}\) is invertible. Define \(\tilde{f}(m) := \widetilde{M}(P\widetilde{M})^{-1} m\) for \(m\in\mathbb{F}_p^k\). We have

1. \(\tilde{f}(\mathbb{F}_p^k) = \widetilde{M}\mathbb{F}_p^k = \Pi C\);

2. The first \(k\) coordinates of \(\tilde{f}(m)\) equal \(P\tilde{f}(m) = P\widetilde{M}(P\widetilde{M})^{-1}m = m\).

Thus \(\tilde{f}\) is a systematic encoder for the permuted code \(\Pi C\), witnessing that \(\Pi C\) is systematic with the same parameters. Undoing the permutation shows that \(C\) becomes systematic after the fixed coordinate permutation \(\Pi\), as claimed.

References↩︎

---

1. Supported by JSPS KAKENHI Grant Number 24K02903.↩︎

2. Supported by JST SPRING, Japan Grant Number JPMJSP2104.↩︎