A cubic binary certificate bound for both MSR perturbation conventions
ProvedStableMSR.Recovery.Supplement.cubic_instability_certificateclusteringcomputational-complexityoptimization
Let a binary string decode to a valid rational finite metric, a feasible specified partition, and rational . The partition is unstable precisely when the mission's checker accepts a certificate of at most bits. The constant and exponent are uniform over both perturbation conventions and over . The certificate encodes the rational table and an integer label for each point of the competing partition. This quantitative form of the certificate-size assertion in Lemma C.3 counts the bits of the published canonical encoding.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery.Supplement
theorem cubic_instability_certificate (metric : Bool) (w : Bits) (γ : ℚ) (S : SpecifiedInput)
(hd : decodeInstabilityInput w = some (γ,S)) (hγ : 1 ≤ γ) (hS : S.Valid) :
¬ ConventionStable metric S.input.dist S.input.k γ S.partition ↔
∃ y : Bits, y.length ≤ 64 * (w.length + 1)^3 ∧ instabilityCheck metric (w,y) = true := by sorry
end StableMSR.Recovery.Supplement
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix C, Lemma C.3, pp. 25–26 (bounded rational polyhedron and determinant argument). https://arxiv.org/abs/2611.03547