Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory

This paper explores how artificial intelligence, specifically a tool called AlphaEvolve, can help make new discoveries in theoretical computer science, a field that studies the limits of efficient computation. The authors used AlphaEvolve, a large-language-model coding agent, to find novel mathematical structures called "combinatorial structures" that improve upon existing results for two specific hard problems. First, they studied the difficulty of certifying properties of random graphs, using AlphaEvolve to construct special graphs called Ramanujan graphs that helped establish near-optimal limits on our ability to analyze problems like MAX-CUT on these graphs. Second, they tackled the NP-hardness of approximating MAX-k-CUT, where AlphaEvolve discovered new "gadget reductions" that prove it is computationally hard to find approximate solutions for these problems within certain factors, improving previous records for MAX-4-CUT and MAX-3-CUT. A key challenge was that verifying the AI's proposed solutions was extremely slow, but the researchers cleverly used AlphaEvolve itself to optimize the verification process, speeding it up by as much as 10,000 times. https://arxiv.org/pdf/2509.18057