Table 2 parameter envelope has a uniform inverse-fifth bound
ProvedStableMSR.Recovery.parameterEnvelope_boundclusteringperturbation-stabilitysum-of-radii
Let , and let be the exact integer parameters of Table 2, with the ceilings and floor specified there. Define the running-time envelope
There is an absolute real constant , independent of , such that
This numerical statement makes the inverse-fifth exponent in Appendix A.5 explicit. It concerns the parameter bound only; it does not assert that a recovery program has been constructed.
Preamble
import Definitions.Def_StableMSR_Recovery_Parameters set_option autoImplicit false
Formal statement
namespace StableMSR.Recovery
theorem parameterEnvelope_bound : ∃ K : ℝ, 0 < K ∧
∀ ε : ℝ, 0 < ε → ε < 1 → (parameterEnvelope ε : ℝ) ≤ K / ε ^ 5 := by sorry
end StableMSR.Recovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547v1, https://arxiv.org/html/2611.03547v1, Table 2; Appendix A.2 (parameters); Appendix A.5 (total running-time exponent).