Fixed bounded oracle expressions for decoding candidate rows
ProvedStableMSR.Recovery.FewBallRows.row_decoder_expressionalgorithmsclusteringformal-verificationmetric-spaces
One bounded distance-oracle expression for each endpoint type implements the mixed table decoder. Prefix rows are copied. Suffix rows describe a cut and a bounded list of balls. The expressions select a minimum-radius pair for each recovered block. Their syntax is independent of the stability parameter and the dimensions.
Preamble
import Definitions.Def_StableMSR_FewBallRows open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows StableMSR.Recovery.FewBallRows open scoped Classical set_option autoImplicit false set_option maxHeartbeats 1800000 set_option maxRecDepth 10000
Formal statement
theorem StableMSR.Recovery.FewBallRows.row_decoder_expression (w : Bool) :
Form (fun x ρ=>iv (transformed x (ρ 0) (ρ 1) w)) := by
sorrySource
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1, Branch A, Lemmas 3.3 and 3.8, and the proof of Theorem 4.5 in Appendix A. Distance-oracle implementation and certificate encoding for the Prove2Me formalization.