AI Proof WatchKeep up with AI contributions

Complexity of integer all-pairs shortest paths

For all-pairs shortest paths with polynomially bounded integer inputs in the specified word-RAM model, the retained deterministic running-time target is O(n^2.99791). Arithmetic and reduction costs are part of the claim.

Why it matters and what counts as progress

Why it matters: It refines a subcubic exponent within an existing framework, rather than representing a separate new framework for overcoming the cubic barrier.

What counts as progress: A faster all-pairs-shortest-path algorithm in the stated bounded-integer model, with the reduction cost included in the running-time exponent.

How the problem developed

  1. 1962 · Baseline algorithm [1]

    Robert W. Floyd Published a cubic-time all-pairs shortest-path algorithm, a baseline that remained standard for decades.

  2. 2018 · Algorithmic improvement [2]

    Virginia Vassilevska Williams Used the polynomial method to improve general APSP by a superpolylogarithmic factor over cubic time, without obtaining a truly subcubic algorithm.

  3. 5 Oct 2026 · Subcubic algorithm [3]

    Josh Alman and Virginia Vassilevska Williams Reported an O(n^2.9995)-time APSP algorithm for polynomially bounded integer weights in the word-RAM model.

  4. 8 Oct 2026 · Exponent refinement [4]

    Improved-exponents project Reported a deterministic O(n^2.99791) bound under the pinned formalization’s stated input assumptions.

AI contributions 2

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Josh Alman, Virginia Vassilevska Williams

Claude’s original sparse-output thin-matrix multiplication algorithm, as presented in Section 2 and related to the certified 3SUM/APSP theorems. Human-optimized numerical parameters, new reductions, data structures and Hinted OMv extensions retain human credit.

AI involvementAI-autonomous
ImportanceMajor
Technical verificationFormal (Lean)
Human understandingFull
Paper date:

Read the contribution and its assessment →

Sources

  1. Robert W. Floyd · Algorithm 97: Shortest path (1962)
  2. Virginia Vassilevska Williams · From circuit complexity to faster all-pairs shortest paths (2018)
  3. Alman–Vassilevska Williams: algorithms and methodology
  4. Improved-exponents project and contribution scope
  5. Completed Lean solution module
  6. Comparator check log
  7. Formalization project
Website timeline

Publication dates and editorial changes.