# Reinforced Generation of Combinatorial Structures: Hardness of Approximation

arXiv: https://arxiv.org/abs/2509.18057 · HTML: https://mlsanity.com/paper/2509.18057/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 63 references that are in the map.
- First posted on arXiv 22 Sep 2025.

## Builds on (most cited first, 12 of 12)

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Can Large Language Models Be an Alternative to Human Evaluations?](https://mlsanity.com/paper/2305.01937/) (2023)
- [Accelerating scientific discovery with Co-Scientist](https://mlsanity.com/paper/2502.18864/) (2025)
- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [Usefulness of LLMs as an Author Checklist Assistant for Scientific Papers: NeurIPS'24 Experiment](https://mlsanity.com/paper/2411.03417/) (2024)
- [A (Slightly) Improved Approximation Algorithm for Metric TSP](https://mlsanity.com/paper/2007.01409/) (2020)
- [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020)
- [Strongly Refuting Random CSPs Below the Spectral Threshold](https://mlsanity.com/paper/1605.00058/) (2016)
- [Is Planted Coloring Easier than Planted Clique?](https://mlsanity.com/paper/2303.00252/) (2023)
- [New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results](https://mlsanity.com/paper/2505.20219/) (2025)
- [New Inapproximability Bounds for TSP](https://mlsanity.com/paper/1303.6437/) (2013)
- [Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs](https://mlsanity.com/paper/2404.17012/) (2024)

## Built on by (most cited first, 9 of 9)

- [Advancing Mathematics Research with AI-Driven Formal Proof Search](https://mlsanity.com/paper/2605.22763/) (2026)
- [Reinforced Generation of Combinatorial Structures: Ramsey Numbers](https://mlsanity.com/paper/2603.09172/) (2026)
- [Discovering Multiagent Learning Algorithms with Large Language Models](https://mlsanity.com/paper/2602.16928/) (2026)
- [FormalTCS: Benchmarking End-to-End Frontier Formal Theoretical Computer Science Research of Large Language Models](https://mlsanity.com/paper/2608.20153/) (2026)
- [A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search](https://mlsanity.com/paper/2603.08679/) (2026)
- [Deep Research of Deep Research: From Transformer to Agent, From AI to AI for Science](https://mlsanity.com/paper/2603.28361/) (2026)
- [Test-Time Optimization of Physical Query Plans with LLMs](https://mlsanity.com/paper/2602.10387/) (2026)
- [k-server-bench: Automating Potential Discovery for the k-Server Conjecture](https://mlsanity.com/paper/2604.07240/) (2026)
- [Code evolution for link prediction in complex networks](https://mlsanity.com/paper/2606.26132/) (2026)

## Abstract (arXiv)

Can AI based methods help us make advances in complexity theory? We provide evidence towards answering this in the affirmative, using AlphaEvolve (an LLM code mutation agent) to obtain new results in three settings: a) We improve a recent result of Kunisky and Yu to obtain near-optimal upper and (conditional) lower bounds on certification algorithms for MAX-CUT and MAX-Independent Set on random 3- and 4-regular graphs. Our improved lower bounds are obtained by constructing nearly extremal Ramanujan graphs on as many as 163 vertices, and our upper bounds are obtained via analytical arguments. b) We obtain new inapproximability results for MAX-4-CUT and MAX-3-CUT, proving that it is NP-hard to approximate them within factors of 0.987 and 0.9649 respectively, using AlphaEvolve to discover new gadget reductions. Our MAX-4-CUT result improves upon the SOTA of 0.9883, and our MAX-3-CUT result improves on the current best gadget-based inapproximability result of 0.9853, but falls short of the SOTA of 16/17 that relies on a custom PCP (rather than a reduction from ``standard'' Haastad-style PCPs). c) Inapproximability for the metric Traveling Salesman Problem (TSP): We show that it is NP-hard to approximate the minimum cost tour within a factor of 111/110 using AlphaEvolve to discover a new gadget, thus improving the SOTA of 117/116. Along the way, we provide new modular soundness and completeness arguments that can be of independent interest. A key technical challenge we faced: verifying a candidate construction produced by AlphaEvolve is costly (sometimes requiring time exponential in the size of the construction). We used AlphaEvolve itself to evolve the verification procedure to be faster (sometimes by 10,000× for our gadgets). Our results suggest that gadget based proofs would benefit from a pass through AI-based tools to obtain stronger results.