Exact-law dual-Horn thinning sensitivity is at most maximum arity over ε
ProvedStabilityDichotomies.Solvability.dualHorn_thinning_sensitivityconstraint-satisfactionprobability
Let Γ be dual-Horn and 0 < ε ≤ 1. Any solver with the exact greatest-solution thinning law has average sensitivity at most maxArity(Γ)/ε on every satisfiable instance. This is the dual-Horn sensitivity part of the source theorem, in the semantic output-law model; runtime is not asserted.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Thinning noncomputable section open scoped Classical BigOperators Interval open MeasureTheory StabilityDichotomies.Solvability
Formal statement
theorem StabilityDichotomies.Solvability.dualHorn_thinning_sensitivity (Γ : Language)
(hDualHorn : ∀ R ∈ Γ.relations, ∀ x y : Fin R.arity → Bool,
x ∈ R.tuples → y ∈ R.tuples → (fun i => x i || y i) ∈ R.tuples)
(ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) (A : Solver Γ)
(hLaw : ThinningOutputLaw Γ true ε A)
(V : Type) [Fintype V] (I : Instance Γ V) (hSat : Satisfiable I) :
averageSensitivity A I ≤ (maxArity Γ : ℝ) * ε⁻¹ := by sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, proof of Theorem 4.3, pp. 16–17, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf