Encode feasible roots by fixed labels and nonnegative distances
ProvedStabilityDichotomies.Bijunctive.feasible_root_candidate_encodingFix a graph subinstance contained in a base feasibility instance and a variable. There is a finite set of candidate roots, a fixed Boolean label for each root, and nonnegative root distances, all independent of shifts and later constraints. For every satisfiable feasibility extension and positive shifts, some feasible candidate has positive shifted score, maximizes over all currently feasible candidates, and has label equal to the algorithm output.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_Bijunctive open scoped Classical BigOperators open StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.feasible_root_candidate_encoding {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (G F₀ : Instance Γ V) (v : V)
(hG : ∀ c ∈ G.constraints, c ∈ F₀.constraints) :
∃ (C : Finset (Literal V)) (label : Literal V → Bool) (d : Literal V → ℝ),
(∀ r ∈ C, 0 ≤ d r) ∧
∀ (F : Instance Γ V), (∀ c ∈ F₀.constraints, c ∈ F.constraints) → Satisfiable F →
∀ δ : Literal V → ℝ, (∀ r, 0 < δ r) →
∃ r ∈ C, feasibleLiteral F r ∧
label r = decide (literalScore rep G F δ (v,false) < literalScore rep G F δ (v,true)) ∧
0 < δ r - d r ∧
∀ q ∈ C, feasibleLiteral F q → δ q - d q ≤ δ r - d r := 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, feasibility-root sensitivity step.