An excluded first-stage priority has the cutoff distribution
ProvedStabilityDichotomies.Bijunctive.outside_priority_conditional_eq_cutoffLet a priority be uniformly distributed on , and suppose . Conditional on the priority exceeding , its distribution is uniform on , the same as the algorithm’s cutoff.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw open scoped Classical ENNReal BigOperators open MeasureTheory ProbabilityTheory Set Filter Function StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.outside_priority_conditional_eq_cutoff (ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) :
ProbabilityTheory.cond unitPriorityMeasure (Ioi (1 - ε / 2)) = cutoffMeasure ε := 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, conditioning on the first-stage constraint set.