Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Owned exterior and high queues refresh one vertex with bounded allocation

Proved
NearlyOptimalPPR.Computation.queue_pair_refresh_exec

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

Consider two disjoint owned rank queues for a single recursive level: the exterior queue and the high-residual queue. Assume their contexts, domain membership, queued flags, and current eligibility predicates are represented correctly. Let vvv lie in that domain, let www be the record width, and let rank rrr and array length LLL cover both heap masses through a capacity below 2r2^r2r, with r<Lr<Lr<L. The pair-refresh routine has a finite execution with

t≤42r+56w+203,Mext′≤Mext+1,Mhigh′≤Mhigh+1.t\le42r+56w+203,\qquad M'_{\rm ext}\le M_{\rm ext}+1,\qquad M'_{\rm high}\le M_{\rm high}+1.t≤42r+56w+203,Mext′​≤Mext​+1,Mhigh′​≤Mhigh​+1.

Each queue retains its existing keys and inserts vvv exactly when its corresponding current eligibility predicate holds. The high Boolean and queued flags are restored; the queue objects remain disjoint. At most six fresh integer cells are allocated. Other integer records outside the two owned objects are preserved, and only the designated high Boolean real cell changes. No graph query or output emission occurs, and work increases by exactly ttt.

This contract provides the shared bounded-allocation operation used by residual propagation and sparse solves.

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 queue_pair_refresh_exec (m : SolveModel) {n : ℕ} (g : InputGraph n) (ω : ℕ → Bool)
    (st : MachineState) (hh : st.scalar.halted=false) (width levelBase length N R : ℕ)
    (hw : levelBase+6 < width) (extBase highBase floor : ℤ) (hFloor : 2 ≤ floor)
    (q theta : ℝ) (domain : Finset (Fin n)) (extValid highValid : Finset ℕ)
    (extObj : RankQueueObject st.scalar.integerMemory extBase length (st.scalar.core.ptrs 20) floor)
    (highObj : RankQueueObject st.scalar.integerMemory highBase length (st.scalar.core.ptrs 20) floor)
    (hSep : Disjoint highObj.cells extObj.cells)
    (ctx : ExteriorQueueContext st width levelBase (levelBase+3) length extBase floor q)
    (extData : ExteriorQueueMemory st.scalar.integerMemory st.scalar.core.mem width levelBase (levelBase+3) q domain extValid extObj.keys)
    (hZero : ∀ u ∈ domain, st.scalar.integerMemory (vertexRecordAddress width u.val (levelBase+5))=0)
    (hHighDomain : highObj.keys ⊆ domain.image Fin.val)
    (hHighFlags : QueuedFlags st.scalar.integerMemory width (levelBase+6) domain highObj.keys)
    (hHighValid : ∀ u ∈ domain, u.val ∈ highValid ↔
      st.scalar.integerMemory (vertexRecordAddress width u.val (levelBase+2)) ≠ 0 ∧
      3*theta*(st.scalar.integerMemory (vertexRecordAddress width u.val 0) : ℝ) ≤
        st.scalar.core.mem (vertexRecordAddress width u.val (levelBase+1)))
    (hHighBase : st.scalar.core.ptrs 128=highBase) (hLevel : st.scalar.core.ptrs 89=(levelBase : ℤ))
    (hOne : st.scalar.core.regs 31=1) (hTheta : st.scalar.core.regs 47=theta)
    (v : Fin n) (hv : v ∈ domain) (hVertex : st.scalar.core.ptrs 40=(v.val : ℤ))
    (hExtMass : extObj.mass ≤ N) (hHighMass : highObj.mass ≤ N) (hCap : R < length) (hPow : N < 2^R) :
    ∃ steps out,
    ∃ newExt : RankQueueObject out.scalar.integerMemory extBase length (out.scalar.core.ptrs 20) floor,
    ∃ newHigh : RankQueueObject out.scalar.integerMemory highBase length (out.scalar.core.ptrs 20) floor,
      MachineEval m g ω queuePairRefreshCode st steps out ∧ steps ≤ 42*R+56*width+203 ∧
      newExt.keys=(if v.val ∈ extValid then insert v.val extObj.keys else extObj.keys) ∧
      newHigh.keys=(if v.val ∈ highValid then insert v.val highObj.keys else highObj.keys) ∧
      newExt.mass ≤ extObj.mass+1 ∧ newHigh.mass ≤ highObj.mass+1 ∧
      ExteriorQueueMemory out.scalar.integerMemory out.scalar.core.mem width levelBase (levelBase+3) q domain extValid newExt.keys ∧
      newHigh.keys ⊆ domain.image Fin.val ∧ QueuedFlags out.scalar.integerMemory width (levelBase+6) domain newHigh.keys ∧
      Disjoint newHigh.cells newExt.cells ∧ st.scalar.core.ptrs 20 ≤ out.scalar.core.ptrs 20 ∧
      out.scalar.core.ptrs 20 ≤ st.scalar.core.ptrs 20+6 ∧
      (∀ z ∈ newExt.cells ∪ newHigh.cells, z < st.scalar.core.ptrs 20 → z ∈ extObj.cells ∪ highObj.cells) ∧
      (∀ other : Fin n, ∀ field < width, field ≠ levelBase+3 → field ≠ levelBase+6 →
        out.scalar.integerMemory (vertexRecordAddress width other.val field)=st.scalar.integerMemory (vertexRecordAddress width other.val field)) ∧
      (∀ z, 0 ≤ z → z < st.scalar.core.ptrs 20 → z ∉ extObj.cells ∪ highObj.cells → out.scalar.integerMemory z=st.scalar.integerMemory z) ∧
      out.scalar.core.mem=Function.update st.scalar.core.mem (vertexRecordAddress width v.val (levelBase+4))
        (if st.scalar.integerMemory (vertexRecordAddress width v.val (levelBase+2))=0 then 0 else
          if 3*theta*(st.scalar.integerMemory (vertexRecordAddress width v.val 0) : ℝ) ≤
            st.scalar.core.mem (vertexRecordAddress width v.val (levelBase+1)) then 1 else 0) ∧
      out.scalar.queries=st.scalar.queries ∧ out.work=st.work+steps ∧ out.output=st.output ∧
      out.scalar.halted=false ∧ out.scalar.core.ptrs 0=0 := 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