Charge an oracle sum over points, blocks, or rows
ProvedStableMSR.Recovery.OracleQueries.axis_sum_machinealgorithmsclustering
A bounded scan simultaneously sums the integer and real components of its body, preserving its input registers and integer table. The running time is polynomial in the axis sizes.
Preamble
import Definitions.Def_StableMSR_OracleQueries open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open Polynomial
Formal statement
theorem StableMSR.Recovery.OracleQueries.axis_sum_machine (a : Axis) (f : Term) (h : Engine f) :
Engine (fun x ρ=>∑i ∈ Finset.range (x.size a), f x (push i ρ)) := by
sorry
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1 and Theorem 1.1. Finite deterministic RAM implementation and ball-cover certification.