AI as a research partner: Advancing theoretical computer science with AlphaEvolve

Google Research · 9 months ago

Google DeepMind's AlphaEvolve system uses language models to iteratively evolve code and discover new mathematical structures in complexity theory. The system improved the inapproximability bound for the MAX-4-CUT problem from 0.9883 to 0.987 and discovered Ramanujan graphs with up to 163 nodes, with all results computationally verified for correctness. AI can now assist theoretical computer science research by generating proof components rather than full proofs, enabling discoveries that advance the field's understanding of computational hardness.