Details

A Human Exposition of Result #138 (Subset Sum in Time O(2^{0.49n}), What That Means, and How We Got There)

On October 6, 2026, OpenAI announced that an internal AI model had made progress on hundreds of open problems in mathematics and theoretical computer science. Rough preprints of the results were released to the public in a GitHub repository and mathematicians have spent the subsequent weeks verifying, explaining, simplifying, and building upon them.

Tim Randolph will focus on Result #138, a faster exact algorithm for the NP-Complete Subset Sum problem. He will summarize the history of prior work on exact algorithms for this problem, including the genesis of several important ideas and the runtime "barrier" at time 2^{0.5n}. He will then outline how these ingredients are combined in the OpenAI proof and the simultaneous work of Li and Ye.

Speaker

Tim Randolph is an assistant professor of computer science at Harvey Mudd College. Prior to Harvey Mudd, he received his PhD in the Theory of Computation Group at Columbia University.