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 Access

Speakers

Josh Alman, Columbia University