Inside-mask deletion costs regroup by the remaining first-stage mask
ProvedStabilityDichotomies.Bijunctive.first_mask_inside_deletion_cost_regroupAssign an arbitrary real cost to each remaining first-stage mask and deleted occurrence. Average the costs of deletions inside the first-stage mask using their exact independent-priority probabilities. Regrouping each mask by deleting the chosen occurrence produces the corresponding average over masks excluding that occurrence, with the exact factor for positive . The formal identity is cross-multiplied, so it also holds at .
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.first_mask_inside_deletion_cost_regroup {α : Type} [Fintype α] [DecidableEq α]
(ε : ℝ) (hε0 : 0 ≤ ε) (hε1 : ε ≤ 1) (cost : (α → Bool) → α → ℝ) :
let P : (α → Bool) → ℝ := fun m => (Measure.pi (fun _ : α => unitPriorityMeasure)
(Set.univ.pi (fun i => if m i then Iic (1 - ε / 2) else Ioi (1 - ε / 2)))).toReal
(ε / 2) * (∑ c : α, ∑ m : α → Bool, if m c then P m * cost (Function.update m c false) c else 0) =
(1 - ε / 2) * (∑ c : α, ∑ m : α → Bool, if m c then 0 else P m * cost m c) := 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, inside-first-stage deletion averaging.