Date: October 26, 2026
Title: Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
Speaker: Josh Alman, Associate Professor of Computer Science, Columbia University
Abstract: 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
Bio: Josh Alman is an Associate Professor of Computer Science at Columbia University, where he works on algorithm design and complexity theory, focused especially on algebraic techniques and their applications.