Average sensitivity of the exact bijunctive output law
OpenStabilityDichotomies.Bijunctive.bijunctive_output_sensitivityconstraint-satisfactionprobability
Fix correct bounded two-CNF representations. There is C > 0 such that, for every 0 < ε ≤ 1, every solver with the exact Definition 4.8 product-measure output law has average sensitivity at most C ε⁻¹ log |V| on every satisfiable instance with at least two variables. This is the sensitivity half of Theorem 4.9; its coupling, path and root-change bounds remain open.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw noncomputable section open scoped Classical open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.bijunctive_output_sensitivity (Γ : Language) (rep : TwoCNFRepresentation Γ) :
∃ C : ℝ, 0 < C ∧ ∀ ε : ℝ, 0 < ε → ε ≤ 1 →
∀ A : Solver Γ, BijunctiveOutputLaw Γ rep ε A →
∀ (V : Type) [Fintype V] (I : Instance Γ V), Satisfiable I →
2 ≤ Fintype.card V →
averageSensitivity A I ≤ C * ε⁻¹ * Real.log (Fintype.card V : ℝ) := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean Constraint Satisfaction Problems, STOC 2027 submission #535, proof of Theorem 4.9, pp. 19–21, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf