Uniform polynomial-time RAM compilation of a bounded sum
ProvedStableMSR.Recovery.Compiler.BoundedSum.bounded_sum_register_enginealgorithmsclusteringderandomization
Evaluate the bound once and run a counted loop with a fresh index pointer. The body has access to that index and the original environment. Its polynomial time and value bounds compose with the bound polynomial.
Preamble
import Definitions.Def_StableMSR_BoundedSumRAM open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.Compiler.BoundedSum open Polynomial
Formal statement
theorem StableMSR.Recovery.Compiler.BoundedSum.bounded_sum_register_engine (f g : Env→ℕ) (hf : Engine f) (hg : Engine g) :
Engine (fun ρ=>∑ i ∈ Finset.range (f ρ),g (push i ρ)) := by
sorry
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix B, Theorem B.2. Charged deterministic RAM implementation.