Exact partition witnesses for equal list-valued signatures in polynomial bit time
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.binary_key_partitionalgorithmsclusteringcomputational-complexity
The algorithm groups points according to equal variable-length lists of naturals. Each nonempty fiber occurs once. The partition and pairwise membership equivalence are exact, with polynomial bit cost including comparisons of long keys.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_CoarseScan 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.binary_key_partition :
Poly (fun z : Input × List Block => keyFibers z.1 z.2) ∧
∀ (I : RationalInput) (_ : I.Valid) (ks : List Block) (_ : ks.length=I.n),
Represents I.n Finset.univ (keyFibers (fieldsOf I) ks) ∧ ∀ x y : Point I.n,
sameRow (keyFibers (fieldsOf I) ks) x y ↔ ks[x.val]?.getD [] = ks[y.val]?.getD [] := 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