This paper explores the use of AI to discover novel combinatorial structures that improve the efficiency limits of algorithms. Specifically, we study two settings using the LLM coding agent AlphaEvolve. First, we improve on the recent results of Kunisky and Yu to obtain near-optimal upper and (conditional) lower bounds on the average case difficulty of the authentication algorithms for MAX-CUT and MAX-Independent Sets in random 3-regular and 4-regular graphs. The improved lower bounds are obtained by constructing near-extreme Ramanujan graphs for up to 163 nodes using AlphaEvolve. Furthermore, we strengthen the upper bounds through analytical arguments, reducing the computational complexity of these problems to three decimal places. Second, we use AlphaEvolve to discover novel gadget reductions, yielding new approximation impossibility results for MAX-4-CUT and MAX-3-CUT. The MAX-4-CUT result improved the state-of-the-art at 0.9883, and the MAX-3-CUT result improved the current best gadget-based approximability result at 0.9853, but failed to improve the state-of-the-art at 16/17, which relies on a custom PCP rather than gadget reduction. Verifying candidate structures generated by AlphaEvolve often required exponential time, a challenge we addressed by accelerating the verification process by up to 10,000x using AlphaEvolve itself. Finally, we discuss criteria for evaluating AI assistance in proof development.
