Kingy AI
Subscribe, 2.1M subscribersWork with Kingy

Breakthrough Tracker record

Polynomial improvements refute the standard 3SUM and APSP hypotheses

Alman and Vassilevska Williams give deterministic O(n^1.9992) time for polynomial-size integer 3SUM and O(n^2.9995) time for directed APSP with polynomially bounded integer weights, yielding the first fixed-polynomial exponent improvements over the textbook bounds in those models.

← Back to the filtered Breakthrough Tracker

Stable ID
cs-3sum-apsp-polynomial-improvements-2026
Revision
cs-3sum-apsp-polynomial-improvements-2026.v1
Field
Theoretical computer science · Fine-grained complexity, graph algorithms and algebraic algorithms
Evidence
Tier 1 · Peer reviewed: No
Record state
Provisional · Formalization-backed provisional algorithms
Last checked

AI role

The paper says an Anthropic Claude model discovered the core algorithm. The human authors understood, simplified, strengthened and extended it, derived consequences and took responsibility. Claude also produced a Lean certification of the headline results.

Record details

Problem or result
Truly subquadratic 3SUM and truly subcubic all-pairs shortest paths
Authors
Josh Alman and Virginia Vassilevska Williams
Institutions
Columbia University; Massachusetts Institute of Technology
Result date
First-version preprint submitted October 5, 2026; independent follow-ups submitted later in October

Why it matters

The result overturns two central fine-grained hardness hypotheses in their standard polynomially bounded integer models and transfers through established reductions to a broad family of graph and geometric problems.

Limits

The exponent gains are small and asymptotic, with restrictions on input size and weight models; they are not evidence of practical speedups at ordinary input sizes. The preprint and supplied Lean artifact are not peer review, although independent follow-up manuscripts reproduce and simplify the route.

Sources

  1. Primary: Alman and Vassilevska Williams 3SUM and APSP algorithms
  2. Formal proof: Anthropic formalization of the headline claims
  3. Independent follow-up: Karingula and Lovett simplified proof
  4. Independent extension: Follow-up improvement for thin selected-entry matrix products

Correction and revision history

  1. 2026-10-19 — Added after primary-source, scope, status, AI-role and limitation review.

Machine-readable: JSON v1 · CSV v1 · Schema v1

This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.