Existence and sensitivity bound for the thinning output law
ProvedStabilityDichotomies.Solvability.thinning_law_and_sensitivityalgorithmsconstraint-satisfactionprobability
For a finite Horn or dual-Horn language Γ, there is a constant C > 0 depending only on Γ and the case such that, for each 0 < ε ≤ 1, there exists a solver with the exact output law of Definition 4.2 and average sensitivity at most C/ε on every satisfiable instance. This is the output-law existence and sensitivity portion of Theorem 4.3, expressed in the semantic solver model. The executable algorithm and runtime are not modeled.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Thinning noncomputable section open scoped Classical open StabilityDichotomies.Solvability
Formal statement
theorem StabilityDichotomies.Solvability.thinning_law_and_sensitivity (Γ : Language) (b : Bool)
(hΓ : ∀ R ∈ Γ.relations, ∀ x y : Fin R.arity → Bool,
x ∈ R.tuples → y ∈ R.tuples →
(fun i => if b then x i || y i else x i && y i) ∈ R.tuples) :
∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ, 0 < ε → ε ≤ 1 →
∃ A : Solver Γ, ThinningOutputLaw Γ b ε A ∧
∀ (V : Type) [Fintype V] (I : Instance Γ V), Satisfiable I →
averageSensitivity A I ≤ C * ε⁻¹ := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, Definition 4.2 and sensitivity proof of Theorem 4.3, pp. 16–17, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf