Corollary 4 — complete transcript reconstruction at termination
OpenDynEdgeColorLLL.Main.Supplement.corollary_4dynamic-algorithmslovasz-local-lemmap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probability
Use the same truth-table family, old instance, incidence batch and shared randomness tables as for Lemma 5, starting with the completed old static transcript. Suppose the repair first stops after stage , when . Then the stage invariants of Lemma 5 hold for every , with the empty-stage extension, and after the specified cleanup the stored transcript equals the entire new static transcript:
Equality includes all selection sets, resampling bits, clause-falsification bits, counters, stage assignments, resampling totals, last-resampling stages, reported final values and clause last stages. The claim is conditional on termination and supplies the reconstruction guarantee used by Theorem 2.
Differences from the source:
- encoding: The old static transcript is stored before the repair, and recovered entries and assignments use the shared tables → FiniteOld makes the completed old static execution explicit; stored arrays and their readout are given by the repair recurrence; reason: Makes the operational precondition and every recovered quantity explicit without assuming an invariant
- generalization: Section 3 imposes probabilistic LLL and uniform parameter assumptions → The deterministic repair claim is stated for every truth-table family and the completed static transcripts specified here, without numerical LLL hypotheses; reason: The deterministic statement needs only truth-table locality and the actual repair recurrence, and specializes to every completed source execution
Preamble
import Definitions.Def_DynEdgeColorLLL_Main_Supplement_Repair set_option autoImplicit false
Formal statement
namespace DynEdgeColorLLL.Main.Supplement
/-- Corollary 4, printed p. 14 / PDF p. 16: the empty-stage extension and full reconstruction. -/
theorem corollary_4
{X : Type*} [Fintype X] [DecidableEq X] {Ω : X → Type*}
[∀ x, MeasurableSpace (Ω x)] {m : ℕ}
(f : TruthTables X Ω m) (hf : IsTruthTableFamily f)
(old : Fin m → Finset X) (B : Finset (Fin m × X))
(τ : (x : X) → ℕ → Ω x) (hold : FiniteOld f old τ)
(R : ℕ) (hstop : StopsAfter f old B τ R) :
(∀ r : ℕ, 1 ≤ r → RepairInvariants f old B τ (repairAt f old B τ (r - 1)) r) ∧
Reconstructs f (applyBatch old B) τ (cleanupRepair f old B τ R) := by sorry
end DynEdgeColorLLL.Main.Supplement
Source
Sijin Peng, Mohsen Ghaffari, STOC 2027 submission #615 (October 2026), Corollary 4, printed p. 14 (PDF p. 16)