Excluded priorities and the cutoff are conditionally iid
ProvedStabilityDichotomies.Bijunctive.conditional_excluded_priorities_and_cutoff_joint_lawConditional on any first-stage occurrence mask, the priorities of excluded occurrences and the common cutoff are mutually independent and all have the same uniform law on . This is the joint random input required for the random-order comparison in 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_priorities_and_cutoff_joint_law {α : Type} [Fintype α]
(ε : ℝ) (hε : 0 < ε) (hε1 : ε ≤ 1) (m : α → Bool) :
Measure.map (fun z : (α → ℝ) × ℝ => (fun i : {i // m i = false} => z.1 i, z.2))
(ProbabilityTheory.cond ((Measure.pi (fun _ : α => unitPriorityMeasure)).prod (cutoffMeasure ε))
((Set.univ.pi (fun i => if m i then Iic (1 - ε / 2) else Ioi (1 - ε / 2))) ×ˢ Set.univ)) =
(Measure.pi (fun _ : {i // m i = false} => cutoffMeasure ε)).prod (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.