Theorem E.6 — uniform box robustness of the parity-trap B&B reduction
OpenAggCG.Supplement.theorem_E_6algorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let all block sizes be positive odd integers, and let . If , every permitted independent multiplicative perturbation and every produce exactly the same stage decisions, visited parity subtrees, and generated-node count as the unperturbed parity-trap program.
For clause block sizes and final block , every complete run satisfies
with , pointwise even at dyadic ties.
Differences from the source:
- encoding: the source describes an exact solver that may choose any fractional parity variable → Lean represents it by a branch-and-bound transition relation and quantifies over every complete run; reason: this preserves every allowed branching choice and makes the claimed run-invariant node count literal
Preamble
import Mathlib import Definitions.Def_CookLevin_Satisfiability import Definitions.Def_AggCG_Supplement_parityTrapMILP import Definitions.Def_AggCG_Supplement_clauseProbeMILP
Formal statement
namespace AggCG.Supplement
/-- **Theorem E.6** (Uniform box robustness; Sharma, *Computational Complexity of Data-Driven Configuration
for Integer Programming, Clustering, and Learning Algorithms*, STOC 2027 submission (manuscript sha256
f7ea0248…), p.30, PDF p.31), for the perturbed parity-trap MILP `Q^η(k_1, …, k_n)` of (4) with
`n = T + 1` positive odd block sizes, `K = max_j k_j`, and the exact LP-based solver of §E.3 (no presolve,
cuts or heuristic, no initial incumbent, both children created, least-indexed fractional selector else any
fractional parity variable, Appendix H score-mixture node selection reading the block sizes, LP-bound
pruning). Let `0 ≤ ε ≤ 1/(1000(n + K))`. For every perturbation `η` of every designated nonzero entry with
`|η| ≤ ε` and every `θ ∈ [0, 1]`:
(1) a complete run exists, and every complete run on `Q^η` has the same stage decisions (at each stage,
whether the trap was processed before its continuation), the same visited parity subtrees (the trap roots
branched on) and the same generated-node count as every complete run on the unperturbed `Q^0`;
(2) in particular, if `k_j = k_j(C) ∈ {1, 3, 5}` encodes a clause `C` for `j ≤ T` (eq. (15)) and the last
block has size `K = k∗`, then with `b = B(θ)` the induced word,
`TreeSize_θ(Q^η_C) = 2T + 3 + Σ_{j=1}^T h(k_j(C)) b_j + h(k∗)·1{C(b) = false}`, `h(2r + 1) = 2(C(2r+2, r+1) − 1)`,
pointwise for all perturbations and all `θ`, dyadic ties included.
**Formalization Note** The controller is `ctrlSel` with the final rule reading the clause from the block
sizes (`sizesClauseFalse`); `B(θ)` is `dyadicWord θ`. A run records processed and branched nodes, so (1)
compares the recorded stage decisions `ctrlBit`, the branched trap roots, and the final generated count
(deferred traps tie at score `−3` and are pruned in any order, so the full processing order is not
compared). Clauses have at most three literals on distinct variables below `T`. -/
theorem theorem_E_6 :
(∀ (T : ℕ) (k : Fin (T + 1) → ℕ), (∀ j, Odd (k j)) → ∀ ε : ℝ, 0 ≤ ε →
ε ≤ 1 / (1000 * ((T + 1 : ℕ) + (Finset.univ.sup k : ℕ) : ℝ)) →
∀ η : TrapPert T k, η.Bounded ε → ∀ θ ∈ Set.Icc (0 : ℝ) 1,
(∃ ρ, BBComplete (parityTrapMILP T k η)
(ctrlSel EVar.x EVar.IsY (sizesClauseFalse T k) θ) (ctrlBranch EVar.x EVar.IsY) ρ) ∧
∀ ρ ρ₀ s s₀,
BBComplete (parityTrapMILP T k η)
(ctrlSel EVar.x EVar.IsY (sizesClauseFalse T k) θ) (ctrlBranch EVar.x EVar.IsY) ρ →
BBComplete (parityTrapMILP T k (TrapPert.zero T k))
(ctrlSel EVar.x EVar.IsY (sizesClauseFalse T k) θ) (ctrlBranch EVar.x EVar.IsY) ρ₀ →
ρ.getLast? = some s → ρ₀.getLast? = some s₀ →
(∀ i ≤ T, ctrlBit EVar.x s i = ctrlBit EVar.x s₀ i) ∧
(∀ j ≤ T, trapNode EVar.x j ∈ s.expanded ↔ trapNode EVar.x j ∈ s₀.expanded) ∧
s.gen = s₀.gen) ∧
(∀ (T : ℕ) (C : CookLevin.Clause) (kstar : ℕ), ProbeClause 3 T C → Odd kstar →
(∀ j : Fin (T + 1), clauseSizes T C kstar j ≤ kstar) → ∀ ε : ℝ, 0 ≤ ε →
ε ≤ 1 / (1000 * ((T + 1 : ℕ) + kstar : ℝ)) →
∀ η : TrapPert T (clauseSizes T C kstar), η.Bounded ε → ∀ θ ∈ Set.Icc (0 : ℝ) 1, ∀ ρ s,
BBComplete (parityTrapMILP T (clauseSizes T C kstar) η)
(ctrlSel EVar.x EVar.IsY (sizesClauseFalse T (clauseSizes T C kstar)) θ)
(ctrlBranch EVar.x EVar.IsY) ρ → ρ.getLast? = some s →
s.gen = 2 * T + 3 + ∑ j : Fin T,
trapCount (clauseSizes T C kstar j.castSucc) * (if dyadicWord θ j.val then 1 else 0) +
trapCount kstar * (if CookLevin.satisfiesClause (fun i => dyadicWord θ i) C then 0 else 1)) := by sorry
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), Theorem E.6 and eq. (5), p.30, PDF p.31