Excluded priorities are conditionally iid with the cutoff law
ProvedStabilityDichotomies.Bijunctive.conditional_excluded_priority_vector_lawFix an arbitrary first-stage mask. Conditional on that mask, the priority values of all excluded occurrences form an independent sample from the same uniform interval distribution as the cutoff. This is the exact marginal law used to order the excluded constraints in the proof of Theorem 4.9.
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.conditional_excluded_priority_vector_law {α : Type} [Fintype α]
(ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) (m : α → Bool) :
Measure.map (fun x : α → ℝ => fun i : {i // m i = false} => x i)
(ProbabilityTheory.cond (Measure.pi (fun _ : α => unitPriorityMeasure))
(Set.univ.pi (fun i => if m i then Iic (1 - ε / 2) else Ioi (1 - ε / 2)))) =
Measure.pi (fun _ : {i // m i = false} => 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.