Polynomial-time serialized integer output on the public RAM
ProvedStableMSR.Recovery.Compiler.BoundedSum.bounded_stream_writeralgorithmsclusteringderandomization
Given bounded-sum descriptions of the output length and its entries, one deterministic program writes the complete stream at consecutive negative addresses and halts within a single uniform polynomial in the unary input size.
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_stream_writer (len : ℕ→ℕ) (value : ℕ→ℕ→ℕ) (hl : Form (fun ρ=>len (ρ 0)))
(hv : Form (fun ρ=>value (ρ 0) (ρ 1))) :
∃ a b : ℕ,0 < a ∧ 0 < b ∧ ∃ P : MinSumFPT.Program, DeterministicProgram P ∧
∀m : ℕ,1 ≤ m → ∃t ≤ a*m^b,
let s := execute P m 0 (fun _ _=>0) t
s.halted=true ∧ s.work ≤ a*m^b ∧ len m ≤ a*m^b ∧
∀j < len m,s.imem (-1-(j:ℤ))=(value m j:ℤ) := 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.