Every predicate of the bijunctive output is measurable
ProvedStabilityDichotomies.Bijunctive.bijunctive_output_predicate_event_measurableFor a finite variable set, the event that the bijunctive algorithm output satisfies any specified property is measurable in the product seed space. In particular, events that a fixed output clause or constraint is violated are measurable.
Preamble
import Definitions.Def_StabilityDichotomies_Approximability_BijunctiveLaw open scoped Classical BigOperators open MeasureTheory Set StabilityDichotomies.Solvability StabilityDichotomies.Bijunctive
Formal statement
theorem StabilityDichotomies.Bijunctive.bijunctive_output_predicate_event_measurable {Γ : Language} {V : Type} [Fintype V]
(rep : TwoCNFRepresentation Γ) (I : Instance Γ V) (ε : ℝ) (P : (V → Bool) → Prop) :
MeasurableSet {s : (Fin I.constraints.card → ℝ) × ℝ × (Literal V → ℝ) |
P (bijunctiveOutput rep I ε s.1 s.2.1 s.2.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.