Theorem 1.2 — uniform local-program upper bound
ProvedNearlyOptimalPPR.Computation.local_program_upper_boundFix the exact-SDDM primitive model, with its positive solve constant and fixed nonnegative integer logarithmic exponent. There exist one admissible finite scalar/query program and positive constants , chosen before the graph, seed and real parameters, such that for every finite simple undirected graph, seed , and , the program terminates almost surely with a nonnegative explicit sparse output satisfying the ACL error guarantee. An isolated source is returned exactly.
Its charged work is measurable and satisfies, with ,
For every , the displayed envelope is at most for all sufficiently large , uniformly over graphs and teleportation parameters. The program receives only the seed and the two real parameters, accesses degrees and neighbors locally, and must implement parameter preparation with its actual charged instructions. The primitive solves only an already prepared sparse SDDM system; assembly, propagation and emitted output remain charged separately.
This is the algorithmic upper-bound branch of Theorem 1.2. Its explicit-output lower bound is an independent theorem.
import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open MeasureTheory open scoped ENNReal
namespace NearlyOptimalPPR.Computation
theorem local_program_upper_bound (m : SolveModel) :
∃ (p : Program) (C c : ℝ), admissible p ∧ 0 < C ∧ 0 < c ∧
(∀ (n : ℕ) (g : InputGraph n) (s : Fin n) (α ε : ℝ),
0 < α → α < 1 → 0 < ε → ε ≤ 1 →
successful m p g s α ε ∧
Measurable (executionWork m p g s α ε) ∧
expectedWork m p g s α ε ≤ ENNReal.ofReal (envelope C c ε)) ∧
subpolynomialEnvelope C c := by sorry
end NearlyOptimalPPR.Computation