Validated surjective output labels decode to an exact-k partition
ProvedStableMSR.Recovery.validLabels_feasibleclusteringperturbation-stabilitysum-of-radii
Let and let be a machine state. Suppose the output label of every point is an integer in , and every one of these labels is used. Decode the labels into their unordered fibers. Then
No metric, stability, or positivity assumption on is needed. The statement includes ; if , its hypotheses are impossible. This is the encoding lemma that derives the feasibility requirement in the recovery specification from the program's validated output labels.
Formalization Note. The labels, their validation, and their decoding are the existing canonical definitions in StableMSR_Recovery_Execution; this theorem adds no alternate output representation.
Preamble
import Definitions.Def_StableMSR_Recovery_Execution set_option autoImplicit false open scoped Classical
Formal statement
namespace StableMSR.Recovery
theorem validLabels_feasible {n k : ℕ} (s : MinSumFPT.State)
(h : ValidLabels n k s) : Feasible Finset.univ k (outputPartition n k s) := by sorry
end StableMSR.Recovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547v1, https://arxiv.org/html/2611.03547v1, Section 1 (exact-k partitions), Section 3 (computational model); elementary encoding consequence of the mission's canonical StableMSR_Recovery_Execution definitions ValidLabels and outputPartition.