APSP below cubic time: equivalence of the two WordRAM models
OpenWordRAM.APSPBridge.apsp_threshold_threeapspfine-grained-complexitysubcubicwordram
For the integer-weighted directed all-pairs shortest-path problem, in which every closed finite walk has nonnegative weight and the input lists edge presence followed by edge weights in row-major order, solvability in the signed-pointer WordRAM model at some rational exponent below is equivalent to solvability in the unsigned-pointer WordRAM model at some rational exponent below . This is the APSP application of the fine-grained transfer theorem. It asserts the existence of algorithms below the cubic threshold on both sides, not equality of exact exponents; a positive subcubic exponent saving is preserved in either direction.
Preamble
import Definitions.Def_WordRAM_APSP_Bridge set_option autoImplicit false
Formal statement
theorem WordRAM.APSPBridge.apsp_threshold_three : WordRAM.APSPBridge.APSPBelow TrulySubcubicAPSP.APSP 3 ↔ WordRAM.APSPBridge.WordRAMBelow TrulySubcubicAPSP.APSP 3 := by sorry
Source
Josh Alman and Virginia Vassilevska Williams, Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs, 2026, https://arxiv.org/abs/2610.06783; mission 'Two WordRAM models: equivalence with polylogarithmic overhead', APSP application.