Proposition 12 — reduction to critical fetch cost
ProvedPagingDelay.PMD.proposition_12delayonline-algorithmsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1paging
Fix the paging parameters, initialization and tie order. Suppose the same constants satisfy for every valid instance. Then for every valid instance,
The hypothesis and conclusion both range over all instances; neither constant can depend on the request list. The comparator is the true infimum over all offline schedules.
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: any tie-breaking rule suffices → all page orders π and all designated initial pages i₀ outside O₀; reason: an arbitrary order resolves simultaneous critical times and equal effective deadlines; no order is fixed
- encoding: Algorithm 1 with instantaneous services and eventual service → explicit transition recursion with |σ|+1 next-event iterations, transient states, optional infima and zero-denominator guards; reason: each critical service serves a pending request, so there are at most |σ|; the guards only totalize undefined inputs, and Lemma 2 states full service rather than assuming it
- encoding: the first nonnegative hitting time |λ| and natural logarithm L → guarded real infimum and L = log(2k+1); reason: on the stated valid domain the hitting set is nonempty, bounded below and closed; k≥1 makes L positive
Preamble
import Definitions.Def_PagingDelay_PMD_Algorithm
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), Proposition 12 — reduction to critical fetch cost, p. 16. -/
theorem proposition_12 (n k : ℕ) (hk : 1 ≤ k) (hkn : k < n)
(w : Fin n → ℝ) (hw : PMDWeights w)
(O₀ : Finset (Fin n)) (hO₀ : O₀.card = k)
(i₀ : Fin n) (hi₀ : i₀ ∉ O₀) (π : Fin n ≃ Fin n)
(ρ c : ℝ) (hρ : 0 ≤ ρ) (hc : 0 ≤ c)
(hbound : ∀ σ : Instance n, ValidInstance σ →
ENNReal.ofReal (criticalFetch w (run k w O₀ i₀ π σ)) ≤
ENNReal.ofReal ρ * optimum k w O₀ σ + ENNReal.ofReal c) :
∀ σ : Instance n, ValidInstance σ →
ENNReal.ofReal (fractionalFetch w (run k w O₀ i₀ π σ)) +
fractionalDelay k (run k w O₀ i₀ π σ) σ ≤
ENNReal.ofReal (23 * ρ) * optimum k w O₀ σ +
ENNReal.ofReal (23 * c + 21 * ∑ i, w i) := 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), Proposition 12 — reduction to critical fetch cost, p. 16. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/453.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.