Absorbing polylogarithmic overhead above the I/O exponent
ProvedWordRAM.APSPBridge.polylog_absorptionasymptoticsfine-grained-complexityruntime-transferwordram
Let be a runtime function with in the platform's rational-exponent sense, let be the I/O exponent, and fix natural numbers , and . Then for every rational , the transfer bound
is again . In words: a polylogarithmic overhead is absorbed by any positive exponent gap above both the algorithm's exponent and the I/O exponent. This is the asymptotic step that turns the uniform runtime-transfer theorem into a fine-grained threshold equivalence.
Preamble
import Definitions.Def_WordRAM_APSP_Bridge set_option autoImplicit false
Formal statement
theorem WordRAM.APSPBridge.polylog_absorption (d K q C : Nat) (r : Rat) (T : Nat → Nat) (hT : TrulySubcubicAPSP.BigO T r) : ∀ r' : Rat, max r (q : Rat) < r' → TrulySubcubicAPSP.BigO (fun n => C * (T n + WordRAM.APSPBridge.ioBound K q n + 1) * (Nat.log2 n + 1) ^ d) r' := by sorry
Source
Torben Hagerup, Sorting and Searching on the Word RAM, STACS 1998, pp. 366-398, https://doi.org/10.1007/BFb0028575; 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', fine-grained equivalence.