Uniform polynomial real-distance RAM decoding of factorized regional ball certificates
ProvedStableMSR.Recovery.RegionalBallDP.decode_regional_menusalgorithmsclusteringdynamic-programmingformal-verification
Decode all certified terminal states simultaneously, returning a global feasible k-ball row of cost at most every represented regional assembly. Runtime is polynomial in the size of the explicit menu table even when it represents exponentially many regional combinations.
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.decode_regional_menus :
∃p : Polynomial ℕ,∃cmd : Cmd,∀(x : World) (s : Store),0<x.k → 0<x.n → shape x → 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 ∧ endpoints y ∧ ∀v,vertex x v → InTable x v → ∀u,Route x v u →
good y v ∧ score y v≤weight x x.k u := 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.