Polynomial distance-RAM execution of all regional relaxation rounds
ProvedStableMSR.Recovery.RegionalBallDP.regional_table_machinealgorithmsclusteringdynamic-programmingformal-verification
A single deterministic distance-oracle RAM program initializes the table, executes exactly H simultaneous Bellman updates for H table rows, and normalizes the output. A full mathematical history witnesses those updates. The polynomial is uniform in the dimensions, metric and table contents.
Preamble
import Definitions.Def_StableMSR_RegionalBallDP open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows StableMSR.Recovery.FewBallRows open StableMSR.Recovery.RegionalBallDP open scoped Classical set_option autoImplicit false set_option maxHeartbeats 2200000 set_option maxRecDepth 12000
Formal statement
theorem StableMSR.Recovery.RegionalBallDP.regional_table_machine :
∃p : Polynomial ℕ,∃cmd : Cmd,∀(x : World) (s : Store),0<x.k → 0<x.rows → Ready x s →
∃t z,Executes x.dist cmd s t z ∧ z≤p.eval x.cap ∧
let y:=worldOf x.k x.rows x.dist t
Ready y t ∧ ∃h : ℕ→ℕ→ℤ,
Writes x (withMem x (h 0)) seedTable ∧
(∀i<x.rows,Writes (withMem x (h i)) (withMem x (h (i+1))) tick) ∧
Writes (withMem x (h x.rows)) y clean := by
sorrySource
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1, equation (2), and Appendix A.4–A.6. Real-distance oracle implementation and witness reconstruction for the Prove2Me recovery mission.