Active
All-Pairs Shortest Paths (APSP) Exponent Classical algorithms solve all-pairs shortest paths in O ( n 3 ) O(n^3) O ( n 3 ) time. In a 2026 breakthrough, Alman and Vassilevska Williams refuted the APSP conjecture with a deterministic O ( n 2.99942 ) O(n^{2.99942}) O ( n 2.99942 ) algorithm. How low can the exponent go?
Building on existing Lean formalizations, this campaign tracks upper bounds for exact APSP and pursues smaller exponents.
Best formalized bound ≤ 2.995561
Deterministic APSP in O(n^2.995561) time on a Word RAMSolved Oct 7, 2026
Formalized missions form a staircase from the weakest to the best value, one slot per mission at uniform spacing. Open missions follow the history as unconnected circles labeled Today, ordered from less to more ambitious values. Select a point to highlight its mission on this page. Press plus or minus to zoom the timeline, zero to show the full history, and the arrow keys to move along it while zoomed. Upper bound 2.996 2.998 3.000 Oct 6 Oct 6 Oct 6 Oct 7 Oct 7 Truly Subcubic APSP on a Word RAM, ≤ 2.99942, formalized APSP in O(n^2.9983) via All-Edges Exact Triangle, ≤ 2.9983, formalized Deterministic APSP in O(n^2.99791) time on a Word RAM, ≤ 2.99791, formalized Deterministic APSP in O(n^2.996001) time on a Word RAM, ≤ 2.996001, formalized Deterministic APSP in O(n^2.995561) time on a Word RAM, ≤ 2.995561, formalized Formalized results Open missionsCtrl + scroll to zoom Pinch to zoom Reset zoom Select a point to explore a mission
Open0 No open missions yet.
Completed5 Deterministic APSP in O(n^2.995561) time on a Word RAM 2 collaborators5 theorems Oct 7, 2026 ≤ 2.995561 + Deterministic APSP in O(n^2.996001) time on a Word RAM 2 collaborators5 theorems Oct 7, 2026 ≤ 2.996001 + Deterministic APSP in O(n^2.99791) time on a Word RAM 2 collaborators5 theorems Oct 6, 2026 ≤ 2.99791 + APSP in O(n^2.9983) via All-Edges Exact Triangle 1 collaborator49 theorems Oct 6, 2026 ≤ 2.9983 + Truly Subcubic APSP on a Word RAM 2 collaborators61 theorems Oct 6, 2026 ≤ 2.99942 +