Computer Science/Discrete Mathematics Seminar I
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
I’ll talk about new faster algorithms for 3SUM, APSP, and many more problems. They all follow from one new algorithm for quickly computing certain entries of a matrix product. That algorithm was found by Anthropic using an internal model of Claude. They then contacted me and Virginia Vassilevska Williams to understand and properly write up the algorithm.
I’ll talk about the algorithm itself, what it means for fine-grained complexity, and the experience of being contacted by Anthropic and putting this paper together.
Paper on arXiv: https://arxiv.org/pdf/2610.06783
Date & Time
November 30, 2026 | 11:00am – 12:00pm
Add to calendar
11/30/2026 11:00
11/30/2026 12:00
Computer Science/Discrete Mathematics Seminar I
use-title
Topic: Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
Speakers: Josh Alman, Columbia University
More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-i-638
I’ll talk about new faster algorithms for 3SUM, APSP, and many more
problems. They all follow from one new algorithm for quickly computing
certain entries of a matrix product. That algorithm was found by
Anthropic using an internal model of Claude. They then contacted me
and Virginia Vassilevska Williams to understand and properly write up
the algorithm.
I’ll talk about the algorithm itself, what it means for fine-grained
complexity, and the experience of being contacted by Anthropic and
putting this paper together.
Paper on arXiv: https://arxiv.org/pdf/2610.06783
[https://urldefense.com/v3/__https:/arxiv.org/pdf/2610.06783__;!!NubF!K0FMBcmK-4jlQPJlbRXy0scUmfoGSO8heBq23PkYvQCdo4aO65Fm9aSacXo3loAfXGDLnCBrCk5Kbwc$]
Simonyi Hall 101 and Remote Access
a7a99c3d46944b65a08073518d638c23
Location
Simonyi Hall 101 and Remote AccessSpeakers
Josh Alman, Columbia University