Guarded attachment of recovered labels reduces recognition to verification
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.attachment_reductionalgorithmsclusteringcomputational-complexity
Any binary polynomial procedure returning the correct labels on stable inputs induces a polynomial recognition-to-verification map on every input string. Off-promise behavior of the label procedure is unrestricted. The guarded encoding precludes spurious specified instances assembled from malformed strings.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_BinaryRecovery import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.attachment_reduction
(γ : ℚ) (f : Input → List ℕ) (hp : Poly f) (hf : Recovers f γ) :
Poly (attach f) ∧ ∀ w, w ∈ Recognize false γ ↔ attach f w ∈ Verify false γ := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Theorem 1.1, Appendix A.5 (bit complexity), and Proposition C.4. https://arxiv.org/abs/2611.03547