• Sources: primary, discussion
  • Summary: Josh Alman and Virginia Vassilevska Williams posted a 76 page preprint on 2026-10-05 giving deterministic 3SUM in O(n^1.9992) and directed APSP with polynomially bounded integer weights in O(n^2.9995), the first polynomial improvements over the textbook algorithms. If correct the paper refutes the 3SUM and APSP hypotheses, their real-valued versions, the Exact Triangle hypothesis, the Zero-Weight k-Clique hypotheses and three rectangular hinted Online Matrix-Vector conjectures. Everything follows from one new algorithm for thin matrix products, built by modifying a variant of Coppersmith's rectangular matrix multiplication.
  • Why it matters: Those hypotheses are the assumed hardness underneath a large body of fine-grained complexity lower bounds, so a correct result invalidates the conditional part of many published hardness claims, while the speedups are far too small to change any implementation.
  • Follow-up: Watch for peer review or a counterexample to the thin matrix product algorithm.