Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Leaf high-set collection and exact joint solve with heap credit

Proved
NearlyOptimalPPR.Computation.leaf_joint_solve_exec

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

Assume a represented recursive state with valid regions and keys, positive-degree stored active vertices, valid epoch marks, and sufficient queue capacity. Let CCC be the nonempty union of the current cache and high-residual set, hhh the top level, and

S=vol⁡(C)+∣C∣.S=\operatorname{vol}(C)+|C|.S=vol(C)+∣C∣.

The leaf routine has a finite execution representing the source leaf-solve transition. It collects the high set, prepares the cache and right-hand side, performs the exact solve, and refreshes all touched records. Heap mass grows by at most 2(h+1)(∣C∣+S)2(h+1)(|C|+S)2(h+1)(∣C∣+S). With PPP the cleaning coefficient, its charged work plus PM′PM'PM′ is bounded by initial work plus PMPMPM, the explicit leaf preparation/solve/refresh allowances, and one exact-solve charge. The output is preserved and the epoch advances by one.

The heap credit covers stale high entries during collection and prevents their repeated traversal from becoming uncharged work.

Preamble
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime
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 leaf_joint_solve_exec (m : SolveModel) {n : ℕ} (g : InputGraph n) (ω : ℕ → Bool)
    (logical : RecursiveState n) (s : Fin n) (α ε : ℝ) (ell length N rank : ℕ) (epoch : ℤ)
    (st : MachineState) (hh : st.scalar.halted=false)
    (pm : RecursiveMachineMemory g s α ε ell length logical st) (hDepth : logical.top ≤ ell)
    (hα : 0<α ∧ α<1) (hRegion : RegionInvariant logical) (hKeys : KeysInvariant g logical)
    (hStored : (logical.frames logical.top).active ⊆ logical.stored)
    (hNonempty : ((logical.frames logical.top).cache ∪ (logical.frames logical.top).high).Nonempty)
    (hDegree : ∀ v ∈ (logical.frames logical.top).cache ∪ (logical.frames logical.top).high,
      0<g.graph.degree v)
    (hEpoch : st.scalar.core.ptrs 53=epoch)
    (hbound : ∀ v : Fin n, st.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7) ≤ epoch)
    (hMass : pm.queueMass+2*(logical.top+1)*
      (((logical.frames logical.top).cache ∪ (logical.frames logical.top).high).card+
        (volumeNat g ((logical.frames logical.top).cache ∪ (logical.frames logical.top).high)+
          ((logical.frames logical.top).cache ∪ (logical.frames logical.top).high).card)) ≤ N)
    (hCap : rank < length) (hPow : N < 2^rank) :
    let C := (logical.frames logical.top).cache ∪ (logical.frames logical.top).high
    let size := volumeNat g C+C.card
    let P := cleanBodyBound (16*(ell+3)) length rank+2
    let A := (C.card+1)*leafPreparationFactor ell logical.top length rank
    let B := leafSolveUnitCost ell logical.top rank C.card size
    ∃ steps out, ∃ memory : RecursiveMachineMemory g s α ε ell length (compilerLeafSolve m g α logical) out,
      MachineEval m g ω leafJointSolveCode st steps out ∧ steps ≤ P*pm.queueMass+A+B+1 ∧
      memory.queueMass ≤ pm.queueMass+2*(logical.top+1)*(C.card+size) ∧
      out.work+((P*memory.queueMass : ℕ) : ℝ≥0∞) ≤
        st.work+((P*pm.queueMass+(A+B+P*(2*(logical.top+1)*size)) : ℕ) : ℝ≥0∞)+solveCharge m C.card size ∧
      out.output=st.output ∧ out.scalar.halted=false ∧
      (out.scalar.core.ptrs 53=epoch+1 ∧ ∀ v : Fin n,
        out.scalar.integerMemory (vertexRecordAddress (16*(ell+3)) v.val 7) ≤ epoch+1) := 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