Exact rational tests for feasibility, perturbations and competing MSR costs
ProvedStableMSR.Recovery.Supplement.BinaryVerifier.numeric_correctalgorithmsclusteringcomputational-complexity
The finite rational tests accept a specified instance exactly when it is valid. On every valid instance the tests on a proposed table and labeling are equivalent to the formal rational witness relation under each perturbation convention. In particular, relabeling the same partition does not furnish a distinct competitor.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryVerifier set_option autoImplicit false open StableMSR.Recovery StableMSR.Recovery.Supplement
Formal statement
namespace StableMSR.Recovery.Supplement.BinaryVerifier
theorem numeric_correct :
(∀ v : Data, valid v = true ↔ (specified v).Valid) ∧
∀ (metric : Bool) (γ : ℚ) (v : Data) (W : Witness), (specified v).Valid →
(competitive metric γ v W = true ↔ WitnessValid metric γ (specified v) (witness W)) := by sorry
end StableMSR.Recovery.Supplement.BinaryVerifier
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3 and Theorem 5.1. https://arxiv.org/abs/2611.03547