Constructing coarse grid sweep partitions in polynomial bit time
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.coarse_sweep_binary_programalgorithmsclusteringcomputational-complexity
For every valid rational metric input, two rational scales and a grid index, compute the coarse ball-signature partition. The centers and small-component representatives are fixed across indices. This specification has no stability, optimality, or split-count assumption.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_CoarseSweep open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.coarse_sweep_binary_program (γ : ℚ) (hg : 1<γ) (hu : γ<2) :
∃ G : SweepInput→Pack, Poly G ∧ ∀ (I : RationalInput) (_ : I.Valid)
(R L : ℚ), 0<R → 512*R≤L →
SweepSpec I (R:ℝ) (L:ℝ) (((γ:ℝ)-1)*R/4) (fun i => G (fieldsOf I,R,L,i)) := by
sorry
Source
Refinement of the wide-component construction in S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix A.2–A.3, Lemma A.1. The coarse net and uniformly spaced deterministic radius argument are an alternative with a larger parameter-dependent split bound. https://arxiv.org/abs/2611.03547