Theory Seminar Series: Timothy Chan, "3SUM Made Simpler."

Nov 30, 2026   10:00 am  
3403 Siebel Center
Sponsor
Siebel School of Computing and Data Science
Speaker
Timothy Chan
Contact
Chandra Chekuri
E-Mail
chekuri@illinois.edu
Originating Calendar
Siebel School Speakers Calendar

Abstract: Last month, a truly subquadratic algorithm for the 3SUM problem was found by Anthropic, as presented by Alman and Vassilevska Williams. Their algorithm relied on a new subroutine for rectangular matrix multiplication with selected output entries. In this talk, I will describe a different truly subquadratic randomized algorithm for 3SUM for integer inputs, found with the help of AI. It bypasses matrix multiplication techniques but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion–exclusion, and so is conceptually easier to understand. The approach also leads to a refutation of the (integer) k-SUM Hypothesis for all odd k. 

This is joint work with Reina Itakura, Zhiyuan Ma, and Yuancheng Yu.

link for robots only