Compile bounded real-oracle aggregate expressions
ProvedStableMSR.Recovery.OracleQueries.bounded_oracle_expression_compileralgorithmsclustering
Every fixed expression in the query language compiles to a finite structured command whose work is bounded by a polynomial in the point, block, and row counts.
Preamble
import Definitions.Def_StableMSR_OracleQueries open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open Polynomial
Formal statement
theorem StableMSR.Recovery.OracleQueries.bounded_oracle_expression_compiler (f : Term) (h : Form f) : Engine f := 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.