Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Touched-vertex refresh restores complete recursive queue representations

Proved
NearlyOptimalPPR.Computation.pending_touched_refresh_foreign_exec

by Shuze Chen · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

Let a pending recursive memory record represent a logical state whose numeric and domain data are valid, with any missing queue coverage confined to a stored source vertex and its neighbors. Assume exterior/high queue coverage and high Boolean records already hold outside that touched set. Let ddd be the source degree, hhh the top level, w=16(ℓ+3)w=16(\ell+3)w=16(ℓ+3) the record width, and rrr a queue rank covering the stated capacity. The touched-refresh routine has a finite execution returning a complete recursive memory representation, with

t≤(d+1)((h+1)(42r+60w+284)+4w+25)+10,t\le(d+1)((h+1)(42r+60w+284)+4w+25)+10,t≤(d+1)((h+1)(42r+60w+284)+4w+25)+10,

and heap mass increasing by at most 2(h+1)(d+1)2(h+1)(d+1)2(h+1)(d+1). It restores the exterior and high predicates at every relevant level, preserves output and graph-query count, and preserves all nonnegative real-memory cells and the specified foreign integer-buffer frame. Charged work increases by exactly ttt.

The contract permits temporary missing coverage after a numeric update and restores it without scanning the graph.

Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_buffers
open Finset Matrix
open scoped ENNReal
set_option autoImplicit false
noncomputable section
attribute [local instance] Classical.propDecidable
Formal statement
namespace NearlyOptimalPPR.Computation
open SparseQueue
theorem pending_touched_refresh_foreign_exec (m : SolveModel) {n : ℕ} (g : InputGraph n) (ω : ℕ → Bool)
    (s : Fin n) (α ε : ℝ) (ell length N R : ℕ) (logical : RecursiveState n)
    (st : MachineState) (hh : st.scalar.halted=false)
    (pm : MachinePendingKeys g s α ε ell length logical st) (hDepth : logical.top ≤ ell)
    (hActiveDomain : ∀ i ≤ logical.top, (logical.frames i).active ⊆ parentDomain logical i)
    (hExtDomain : ∀ i ≤ logical.top, (logical.frames i).exterior ⊆ parentDomain logical i)
    (hHighDomain : ∀ i ≤ logical.top, (logical.frames i).high ⊆ parentDomain logical i)
    (source : Fin n) (hs : source ∈ logical.stored)
    (hSource : st.scalar.core.ptrs 116=(source.val : ℤ)) (hVertex : st.scalar.core.ptrs 40=(source.val : ℤ))
    (hDegree : st.scalar.core.ptrs 120=((g.neighbors source).length : ℤ))
    (hMass : pm.queueMass+2*(logical.top+1)*((g.neighbors source).length+1) ≤ N) (hCap : R < length) (hPow : N < 2^R)
    (hExtOutside : ∀ i, ∀ hi : i ≤ logical.top,
      (logical.frames i).exterior.image Fin.val \ (insert source (g.neighbors source).toFinset).image Fin.val ⊆ (pm.frames i hi).exteriorObject.keys)
    (hHighOutside : ∀ i, ∀ hi : i ≤ logical.top,
      (logical.frames i).high.image Fin.val \ (insert source (g.neighbors source).toFinset).image Fin.val ⊆ (pm.frames i hi).highObject.keys)
    (hBoolOutside : ∀ i ≤ logical.top,
      HighBooleanRecords st.scalar.integerMemory st.scalar.core.mem (16*(ell+3)) (16*(i+1)) (logical.frames i).theta
        (parentDomain logical i \ insert source (g.neighbors source).toFinset)) :
    ∃ steps out, ∃ memory : RecursiveMachineMemory g s α ε ell length logical out,
      MachineEval m g ω pendingTouchedRefreshCode st steps out ∧
      steps ≤ ((g.neighbors source).length+1)*((logical.top+1)*(42*R+60*(16*(ell+3))+284)+4*(16*(ell+3))+25)+10 ∧
      memory.queueMass ≤ pm.queueMass+2*(logical.top+1)*((g.neighbors source).length+1) ∧
      out.scalar.core.ptrs 40=(source.val : ℤ) ∧ out.scalar.queries=st.scalar.queries ∧
      out.work=st.work+steps ∧ out.output=st.output ∧ out.scalar.halted=false ∧
      (∀ z : ℤ, 0 ≤ z → out.scalar.core.mem z=st.scalar.core.mem z) ∧ PendingIntegerFrame pm (MachinePendingKeys.ofMemory memory) := by sorry
end NearlyOptimalPPR.Computation
Source
Li, Xu, Yang, Zhou, Nearly optimal Personalized PageRank computation, STOC 2027 submission #884, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/884.pdf, Algorithms 1 and 6–9, pp. 5,14–22; charged local-machine realization of the mission computational model.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me