Binary candidate enumeration for the many-large-cluster branch of deterministic recovery
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.many_large_binary_candidatesalgorithmsclusteringcomputational-complexity
For fixed γ between one and two, enumerate polynomially many candidate label vectors on instances having more than a parameter-dependent constant number of large clusters. The remaining algorithmic construction is the split-large-cluster and bounded-treewidth search with the deterministic permutation family (Section 4, Branch B), including the rational bit bound from Appendix A.5.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_LargeBallSearch 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.many_large_binary_candidates (γ : ℚ) (hγ : 1<γ) (hγ' : γ<2) :
∃ (b : ℕ) (F : Input → List (List ℕ)), Poly F ∧
∀ (I : RationalInput) (hI : I.Valid) (O : Partition I.n),
Stable I.dist I.k (γ:ℝ) O → I.k < I.n →
b < (largeClusters I.dist O ((γ:ℝ)-1)).card → Appears F I O := by
sorry
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Lemma 3.8, Section 4 Branch A and Branch B, Appendix A.5, and Proposition C.4. https://arxiv.org/abs/2611.03547