Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definition 3 — rrr-pivot β\betaβ-hop kkk-stretch approximate distance oracles

Definition
PivotADO_OneHop_Supplement_HopOracle

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

combinatoricsgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1theoretical-computer-science

Let G=(V,E)G=(V,E)G=(V,E) be an undirected, unweighted simple graph with shortest-path distance δG\delta_GδG​. Let r,β≥1r,\beta\ge1r,β≥1 be integers and k≥1k\ge1k≥1. An rrr-pivot β\betaβ-hop kkk-stretch ADO for GGG consists of

  1. a weighted undirected graph H=(V,EH,wH)H=(V,E_H,w_H)H=(V,EH​,wH​) with wH(x,y)≥δG(x,y)w_H(x,y)\ge\delta_G(x,y)wH​(x,y)≥δG​(x,y) for every (x,y)∈EH(x,y)\in E_H(x,y)∈EH​, where by convention wH(a,a)=0w_H(a,a)=0wH​(a,a)=0 and wH(x,y)=∞w_H(x,y)=\inftywH​(x,y)=∞ for x≠yx\ne yx=y with (x,y)∉EH(x,y)\notin E_H(x,y)∈/EH​;
  2. a set P(v)⊆VP(v)\subseteq VP(v)⊆V of at most rrr pivots for every v∈Vv\in Vv∈V, with v∈P(v)v\in P(v)v∈P(v),

such that for all u,v∈Vu,v\in Vu,v∈V,

δG(u,v)≤dH,P≤β(u,v)≤k δG(u,v).\delta_G(u,v)\le d^{\le\beta}_{H,P}(u,v)\le k\,\delta_G(u,v).δG​(u,v)≤dH,P≤β​(u,v)≤kδG​(u,v).

Here dH,P≤β(u,v)d^{\le\beta}_{H,P}(u,v)dH,P≤β​(u,v) is the minimum of

wH(u,pu)+∑i=1jwH(pxi−1′,pxi)+∑i=1j−1(wH(pxi,xi)+wH(xi,pxi′))+wH(pv,v)w_H(u,p_u)+\sum_{i=1}^{j}w_H\bigl(p'_{x_{i-1}},p_{x_i}\bigr)+\sum_{i=1}^{j-1}\Bigl(w_H(p_{x_i},x_i)+w_H(x_i,p'_{x_i})\Bigr)+w_H(p_v,v)wH​(u,pu​)+i=1∑j​wH​(pxi−1​′​,pxi​​)+i=1∑j−1​(wH​(pxi​​,xi​)+wH​(xi​,pxi​′​))+wH​(pv​,v)

over all 1≤j≤β1\le j\le\beta1≤j≤β, all vertices x1,…,xj−1∈Vx_1,\dots,x_{j-1}\in Vx1​,…,xj−1​∈V, and all pivots pu∈P(u)p_u\in P(u)pu​∈P(u), pv∈P(v)p_v\in P(v)pv​∈P(v) and pxi,pxi′∈P(xi)p_{x_i},p'_{x_i}\in P(x_i)pxi​​,pxi​′​∈P(xi​), where px0′=pup'_{x_0}=p_upx0​′​=pu​ and pxj=pvp_{x_j}=p_vpxj​​=pv​. This is the weight of the walk u→pu→px1→x1→px1′→⋯→pxj−1→xj−1→pxj−1′→pv→vu\to p_u\to p_{x_1}\to x_1\to p'_{x_1}\to\cdots\to p_{x_{j-1}}\to x_{j-1}\to p'_{x_{j-1}}\to p_v\to vu→pu​→px1​​→x1​→px1​′​→⋯→pxj−1​​→xj−1​→pxj−1​′​→pv​→v with jjj stored hops; the pivot jumps do not count as hops. The space of the oracle is ∣EH∣|E_H|∣EH​∣.

This model is the object of Theorem 2; for β=1\beta=1β=1 it is the one-hop model of the mission's goal.

Formalization Note HHH reuses the published WeightedGraph (a simple graph with symmetric [0,∞][0,\infty][0,∞] edge weights) and its weight, which supplies the conventions wH(a,a)=0w_H(a,a)=0wH​(a,a)=0 and wH=∞w_H=\inftywH​=∞ off stored edges. With x0=ux_0=ux0​=u, xj=vx_j=vxj​=v, the cost is written as ∑i=0j−1(wH(xi,pxi′)+wH(pxi′,pxi+1)+wH(pxi+1,xi+1))\sum_{i=0}^{j-1}\bigl(w_H(x_i,p'_{x_i})+w_H(p'_{x_i},p_{x_{i+1}})+w_H(p_{x_{i+1}},x_{i+1})\bigr)∑i=0j−1​(wH​(xi​,pxi​′​)+wH​(pxi​′​,pxi+1​​)+wH​(pxi+1​​,xi+1​)), which equals (5.5) because wHw_HwH​ is symmetric; the vertices and pivots are indexed by Fin(j+1)\mathrm{Fin}(j+1)Fin(j+1), and the unused entries px0p_{x_0}px0​​, pxj′p'_{x_j}pxj​′​ range over the (nonempty) pivot sets. The minimum is an infimum in [0,∞][0,\infty][0,∞] over this finite family. Stored edges may carry weight ∞\infty∞; they are counted in the space.

Definition code
import Definitions.Def_PivotADO_OneHop_WeightedGraph

set_option autoImplicit false
open scoped Classical ENNReal
noncomputable section

namespace PivotADO.OneHop.Supplement

open PivotADO.OneHop

/-! Definition 3 (r-pivot β-hop k-stretch ADO), Kadria–Roditty, STOC 2027 submission
#584 (October 2026), p.20 (PDF 21), equation (5.5). -/

/-- The weight (5.5) of the walk
`u = x₀ → p'_{x₀} → p_{x₁} → x₁ → p'_{x₁} → ⋯ → p_{x_j} → x_j = v`
with `j` stored hops `p'_{x_i} → p_{x_{i+1}}`. Here `pout i = p'_{x_i}` and
`pin i = p_{x_i}`; the values `pin 0` and `pout (Fin.last j)` are not used.
Every summand uses the stored weight `w_H` (zero on the diagonal, `⊤` off stored edges).
Since `w_H` is symmetric, this is exactly the sum (5.5). -/
def hopWalkCost {V : Type*} (H : WeightedGraph V) {j : ℕ}
    (x pin pout : Fin (j + 1) → V) : ℝ≥0∞ :=
  ∑ i : Fin j, (H.weight (x i.castSucc) (pout i.castSucc) +
    H.weight (pout i.castSucc) (pin i.succ) + H.weight (pin i.succ) (x i.succ))

/-- `d^{≤β}_{H,P}(u, v)`: the minimum of (5.5) over `1 ≤ j ≤ β`, intermediate vertices
`x₁, …, x_{j−1}` and pivots `p_{x_i}, p'_{x_i} ∈ P(x_i)` (which may differ), with
`x₀ = u`, `x_j = v`. -/
def hopEstimate {V : Type*} (H : WeightedGraph V) (pivots : V → Finset V) (β : ℕ)
    (u v : V) : ℝ≥0∞ :=
  ⨅ (j : ℕ) (_ : 1 ≤ j ∧ j ≤ β) (x : Fin (j + 1) → V)
    (_ : x 0 = u ∧ x (Fin.last j) = v) (pin : Fin (j + 1) → V) (pout : Fin (j + 1) → V)
    (_ : ∀ i, pin i ∈ pivots (x i) ∧ pout i ∈ pivots (x i)),
    hopWalkCost H x pin pout

/-- An r-pivot β-hop k-stretch ADO for `G` (Definition 3). The space of the oracle is
`edgeCount storage.graph`, counting every stored edge (including any of weight `⊤`). -/
structure HopOracle {V : Type*} (G : SimpleGraph V) (r β : ℕ) (k : ℝ) where
  storage : WeightedGraph V
  pivots : V → Finset V
  self_mem : ∀ v, v ∈ pivots v
  card_le : ∀ v, (pivots v).card ≤ r
  dominates : ∀ u v, storage.graph.Adj u v → distance G u v ≤ storage.weight u v
  bounds : ∀ u v, distance G u v ≤ hopEstimate storage pivots β u v ∧
    hopEstimate storage pivots β u v ≤ ENNReal.ofReal k * distance G u v

end PivotADO.OneHop.Supplement
Source
Avi Kadria, Liam Roditty, STOC 2027 submission #584 (October 2026), Definition 3 and equation (5.5), p.20 (PDF p. 21); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/584.pdf

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