Each occurrence is violated with probability at most ε
ProvedStabilityDichotomies.Bijunctive.bijunctive_occurrence_violation_seed_boundFor a satisfiable instance, , and any original constraint occurrence, the probability under the exact Definition 4.8 seed law that the output violates that occurrence is at most . The result counts repeated occurrences separately.
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.bijunctive_occurrence_violation_seed_bound {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (hI : Satisfiable I)
(ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) (i : Fin I.constraints.card) :
(bijunctiveSeedMeasure rep I ε
{seed | ¬ (occurrenceAt I i).Satisfied (bijunctiveOutput rep I ε seed.1 seed.2.1 seed.2.2)}).toReal ≤ ε := 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, approximation paragraph.