Theorem 1.2 — local algorithm with uniform expected work
ProvedNearlyOptimalPPR.Computation.uniform_local_algorithmFix an exact-SDDM primitive model. There exist one admissible local scalar/query program and positive constants , fixed before all graph inputs, seeds and parameters, such that every finite simple undirected graph, seed , and receives an almost-surely terminating nonnegative explicit output with the ACL guarantee. An isolated seed is returned exactly.
Writing , the expected charged work satisfies
All parameter preparation, graph queries, sparse-system assembly, boundary propagation and output must be implemented by the program's charged instructions. Exact solves operate only on already prepared sparse SDDM systems.
This is the algorithmic core of the upper bound. Measurability of execution work and the envelope's eventual bound are established separately as general results and combined with this statement in the parent theorem.
import Definitions.Def_NearlyOptimalPPR_Computation_push set_option autoImplicit false open MeasureTheory open scoped ENNReal
namespace NearlyOptimalPPR.Computation
theorem uniform_local_algorithm (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 α ε ∧
expectedWork m p g s α ε ≤ ENNReal.ofReal (envelope C c ε)) := by sorry
end NearlyOptimalPPR.Computation