Specified-partition verification belongs to coNP under both perturbation conventions
ProvedStableMSR.Recovery.Supplement.verification_coNPFor each fixed rational stability factor greater than one, the binary language of valid specified partitions that remain uniquely optimal belongs to coNP. This holds for arbitrary symmetric perturbations and for perturbations that must be metrics. A string that does not encode a valid specified input is outside the language.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_Languages set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery.Supplement
theorem verification_coNP (b : Bool) (γ : ℚ) (hγ : 1 < γ) :
Verify b γ ∈ CSPIdealMem.coNP := by sorry
end StableMSR.Recovery.Supplement
Source
Ravichandran and Reyzin, arXiv:2611.03547, Theorem 5.1(i), proof following Lemma C.3, pp. 25–26.