Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — O(log k)-competitive weighted paging with delay

Proved
PagingDelay.PMD.theorem_1

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1paging

There is an absolute constant C>0C>0C>0 such that, for every number nnn of pages, every 1≤k≤n1\le k\le n1≤k≤n, every positive real weight vector www, and every initial cache O0O_0O0​ of exactly kkk pages, there are a clairvoyant randomized online algorithm AAA starting at O0O_0O0​ and a constant c≥0c\ge0c≥0 with

E[cost⁡(A,σ)]≤Clog⁡(2k+1)Opt⁡(σ)+cfor every valid instance σ.\mathbb E[\operatorname{cost}(A,\sigma)]\le C\log(2k+1)\operatorname{Opt}(\sigma)+c\qquad\text{for every valid instance }\sigma.E[cost(A,σ)]≤Clog(2k+1)Opt(σ)+cfor every valid instance σ.

The probability space, algorithm and additive constant are fixed before the request instance. The optimum ranges over all offline schedules. Requests have arbitrary continuous, nondecreasing, unbounded delay functions, zero at zero. Duplicate requests and simultaneous arrivals are permitted. The full-cache case k=nk=nk=n is included. This is the complete competitive existence claim, without a fractional or dyadic restriction.

Differences from the source:

  • encoding: finite pages, continuous time, finite requests and instantaneous cache walks → Fin n pages, real times, finite request and event lists, and ENNReal costs; reason: same instances; positive weights reduce every finite-cost offline schedule to finitely many fetches without increasing cost
  • reading: O(log k), including cache size one → C log(2k+1) with an absolute C; reason: the paper proves L=log(2k+1); this is comparable to 1+log k for every k≥1, and avoids a zero ratio at k=1
  • encoding: randomized algorithms and their expected costs → probability measures, per-seed online maps and measurable total, fetch and delay cost observables; reason: the usual measurability convention for random costs is explicit; expectations are integrals of random variables rather than arbitrary lower integrals
Preamble
import Definitions.Def_PagingDelay_PMD_Model
Formal statement
namespace PagingDelay.PMD
open scoped BigOperators

/-- Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Theorem 1 — O(log k)-competitive weighted paging with delay, p. 2. -/
theorem theorem_1  :
    ∃ C : ℝ, 0 < C ∧ ∀ (n k : ℕ), 1 ≤ k → k ≤ n →
      ∀ (w : Fin n → ℝ), (∀ i, 0 < w i) →
      ∀ (O₀ : Finset (Fin n)), O₀.card = k →
      ∃ (A : RandomizedAlgorithm n k w O₀) (c : ℝ), 0 ≤ c ∧
      ∀ (σ : Instance n), ValidInstance σ →
      expectedCost A σ ≤ ENNReal.ofReal (C * Real.log (2 * (k : ℝ) + 1)) * optimum k w O₀ σ +
        ENNReal.ofReal c := by sorry

end PagingDelay.PMD
Source
Julian Born, Yann Disser, Linda Thelen, Tight weighted paging with delay via mirror descent, STOC 2027 submission #453 (October 2026), Theorem 1 — O(log k)-competitive weighted paging with delay, p. 2. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/453.pdf
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

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