A bounded query for minimum-cost ball-cover labels
ProvedStableMSR.Recovery.BallCoverCatalog.selector_expressionalgorithmsclustering
Table access, coverage and distinctness tests, exact distance scores, deterministic ties, and label decoding have one fixed expression independent of the stability parameter.
Preamble
import Definitions.Def_StableMSR_BallCoverCatalog open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open Polynomial open StableMSR.Recovery.BallCoverCatalog
Formal statement
theorem StableMSR.Recovery.BallCoverCatalog.selector_expression : Form (fun x ρ=>iv (output x (ρ 0))) := by sorry
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1 and Theorem 1.1. Finite deterministic RAM implementation and ball-cover certification.