A constraint occurrence is omitted with probability ε/2
ProvedStabilityDichotomies.Bijunctive.unit_priority_omission_probabilityFor , a uniform priority on exceeds the graph threshold with probability exactly .
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw open scoped Classical ENNReal open MeasureTheory ProbabilityTheory Set StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.unit_priority_omission_probability (ε : ℝ) (hε : 0 ≤ ε) (hε1 : ε ≤ 1) :
unitPriorityMeasure (Ioi (1 - ε / 2)) = ENNReal.ofReal (ε / 2) := by
sorrySource
Wang and Yoshida, Stability Dichotomies for Boolean CSPs, STOC 2027, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/535.pdf, Definition 4.8 and proof of Theorem 4.9.