Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
- Published
- Source
- arXiv
- Paper number
- 1165
- Field
- Research
- arXiv ID
- 2610.06783
Key points
- For the first time in 50 years, 3SUM was solved polynomially faster, reducing O(n^2) to O(n^1.9992).
- A single thin matrix multiplication algorithm speeds up many problems at once, including APSP and Exact Triangle.
- The AI model Claude discovered the core algorithm, the human authors understood and extended it, and the proofs were verified in Lean 4.
- Several hypotheses of fine-grained complexity theory are refuted, with major impact on lower-bound research.
Paper links
External research summaries. These are not HDATF publications or measured product results.