Polynomial bit complexity of exact-count regional dynamic programming with witnesses
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.exact_count_bit_programalgorithmsclusteringcomputational-complexity
The explicit dynamic program on rational distances, local tables, and a binary point count is polynomial in their encoded lengths. It carries whole partitions for reconstruction. The bound holds even for malformed dimensions and arbitrary large rational values.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_RegionalTables import Definitions.Def_QuantumMaxCutFiniteNumericRuntime open OAI.MetricKMedian.Binary.Automatic open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.exact_count_bit_program :
Poly (fun x : Input × List Table => assemble x.1 x.2) := by
sorry
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 4.1 equation (2), Proposition 4.2 and Appendices A.4–A.6. https://arxiv.org/abs/2611.03547