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

- Sponsor
- Siebel School of Computing and Data Science
- Speaker
- Timothy Chan
- Contact
- Chandra Chekuri
- chekuri@illinois.edu
- Views
- 1
- 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.