The executable binary MSR verifier agrees with the certificate relation on every string
ProvedStableMSR.Recovery.Supplement.BinaryVerifier.check_correctalgorithmsclusteringcomputational-complexity
On every pair of binary strings, the total algorithm agrees exactly with the published mathematical instability checker. The input validator recognizes precisely the strings decoding to a valid specified instance. This includes malformed fields, unreduced rational numbers, incorrect table lengths, and invalid labelings.
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 check_correct :
(∀ metric, check metric = instabilityCheck metric) ∧
∀ raw, specifiedOK raw = true ↔ ∃ S, decodeSpecified raw = some S ∧ S.Valid := 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