An isolated literal’s score equals its own shift
ProvedStabilityDichotomies.Bijunctive.isolated_variable_literal_score_eq_own_shiftFor a satisfiable original instance, a variable outside all constraint scopes, and arbitrary graph and feasibility thinning masks, each of its literal scores equals its own shift. Thus its output is unaffected by changes to either mask.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.isolated_variable_literal_score_eq_own_shift {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (hI : Satisfiable I) (v : V)
(hiso : ∀ c ∈ I.constraints, ∀ k : Fin c.rel.val.arity, c.scope k ≠ v)
(graphMask feasibleMask : Fin I.constraints.card → Bool) (δ : Literal V → ℝ) (b : Bool) :
literalScore rep (thinnedInstance I graphMask) (thinnedInstance I feasibleMask) δ (v,b) =
((δ (v,b) : ℝ) : WithBot ℝ) := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, proof of Theorem 4.9, sensitivity analysis.