Two famous algorithmic speed limits may have cracked
- What it is
- Algorithms claim to beat two long-standing speed barriers: finding three numbers that sum to zero and calculating shortest paths between every pair of points.
- Who did it
- Josh Alman and Virginia Vassilevska Williams; core algorithm discovery credited to an internal Claude model, with later formalization by Anthropic.
- What it could mean
- A crack in two famous speed limits could reshape what researchers think computers can do efficiently. The gains are theoretical and tiny; faster maps or logistics software have not been demonstrated.
See the check plan
Evidence & validation
From announcement to evidence
Discovery recorded. State of Proof has not yet examined this claim.
Read the original work
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs ↗See the proposed checks
Inspect Lemma 11's shared-leaf count and the complete encoding/decoding costs, then the exact reductions and the word-RAM statement. Map the five endpoints and their definitions through both Comparator configurations. Any future replay needs fresh isolated clones, the pinned toolchain, and both Lean and nanoda checks; none occurred here.
No proof docket yet
A docket is the public record of checks and open questions. This paper does not have one yet; the check plan above describes work still to do.
Explore existing proof dockets →
A tiny middle group changes the triangle search
The paper uses sparse tripartite graphs with a much smaller middle group. The highlighted triangle introduces its algorithmic mechanism, not an executed search, weighted instance, or runtime measurement.
Read the source · Section 3.1 · Definition 13, sparse lopsided graphs ↗- What it claims
- Theorem 22 claims deterministic 3SUM in O(n¹.9992), and min-plus product/APSP in O(n².99942), for polynomially bounded integer inputs; APSP excludes negative cycles. Theorem 19 gives Exact Triangle in O(n².9983). Corollary 39 gives Zero-Weight k-Clique in O(n^(k−0.0017 floor(k/3))).
- Why this could matter
- Two famous algorithmic speed limits may have cracked Imagine discovering a shortcut where computer scientists had expected a hard limit. These algorithms claim small asymptotic improvements on two cornerstone problems. Because many other problems are connected to them, the consequences could spread well beyond the original questions.
- If it holds up
- Researchers would revisit conditional speed limits built on 3SUM and shortest paths, and test where the new technique travels.
- If it does not
- The failed estimate, reduction, or formal correspondence would locate which speedup needs repair—not show that every faster algorithm is impossible.
- Impact horizon
- Foundational · Algorithms · Computational complexity · AI-assisted discovery
- Version
- arXiv v1; 2026-10-05.
- Why we tracked it
- source-reviewed mathematical intake, not a completed peer review or homepage feature.
- Highest-risk dependency
- Analyst judgment: the claimed saving must survive every encoding, pruning, tiling and reduction overhead, including uniformity in input magnitude. Source-to-formal correspondence is a separate gate from the correctness of the formal inference. Keep the abstract's rounded APSP exponent 2.9995 distinct from Theorem 22's sharper 2.99942. Integer-input formal endpoints do not certify the paper's separate real-input Las Vegas claims.
- Available artifacts
- A Lean development is pinned at anthropics/formal-math e1a4e6508154ea59f030480661590a9fe3018011, under 3sum-apsp, with Lean 4.33.1 and five named integer-input endpoints. Real-input running times and Section 5.1 are outside those formal endpoints. No State of Proof Lean or Comparator replay has been completed.
- Current boundary
- Intake record only; examination not started.