Expected graph-deletion bit changes are logarithmic
ProvedStabilityDichotomies.Bijunctive.expected_graph_deletion_changes_boundFix a satisfiable feasible-root instance, an occurrence-retention mask, and a variable. Under independent rate- exponential shifts, the number of occurrence deletions from the graph subinstance that change this variable’s score-comparison output is integrable and has expectation at most . Feasible roots are held fixed throughout this graph-deletion step.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.expected_graph_deletion_changes_bound {Γ : Language} {V : Type} [Fintype V] [Nonempty V]
(rep : TwoCNFRepresentation Γ) (I F : Instance Γ V) (hF : Satisfiable F)
(mask : Fin I.constraints.card → Bool) (v : V) (β : ℝ) (hβ : 0 < β) :
let μ := Measure.pi (fun _ : Literal V => expMeasure β)
let C := fun δ : Literal V → ℝ => ∑ j : Fin I.constraints.card,
if decide (literalScore rep (thinnedInstance I (fun i => mask i && decide (i ≠ j))) F δ (v,false) <
literalScore rep (thinnedInstance I (fun i => mask i && decide (i ≠ j))) F δ (v,true)) ≠
decide (literalScore rep (thinnedInstance I mask) F δ (v,false) <
literalScore rep (thinnedInstance I mask) F δ (v,true)) then (1 : ℝ) else 0
Integrable C μ ∧ (∫ δ, C δ ∂μ) ≤ (Real.log (Fintype.card (Literal V)) + 1) / β := 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, first sensitivity step.