While Large Language Models excel at competitive programming and mathematics, their impact on novel research discovery remains limited. This talk introduces AlphaEvolve, an LLM-based agent that discovers complex combinatorial structures to advance the state-of-the-art in hardness of approximation and extremal combinatorics.
We present several new results achieved by AlphaEvolve, including a new metric TSP lower bound of 111/110 (improving upon 117/116) and state-of-the-art lower bounds for classical Ramsey numbers: R(3,13), R(3,18), R(4,13), R(4,14), and R(4,15). Additionally, AlphaEvolve identified novel graph constructions that improve worst-case hardness of approximation for MAX-4-CUT, alongside new average-case hardness bounds for MAX-2-CUT and MAX-Independent Set.
The scale and intricacy of these graphs make them highly unlikely to be discovered via human intuition or traditional solvers alone. Crucially, every discovery includes a machine-verifiable certificate to guarantee validity. We conclude by examining the evolving role of AI in mathematical research, comparing its discovery potential against both human ingenuity and traditional computation.
Joint work with Ansh Nagda (University of California, Berkeley) and Prabhakar Raghavan (Google).
Based on these two papers: https://arxiv.org/abs/2603.09172 and https://arxiv.org/pdf/2509.18057