AlphaEvolve finds gadgets that prove new NP-hardness of approximation bounds for MAX-k-CUT
Google researchers used AlphaEvolve to discover gadget reductions proving it is NP-hard to approximate MAX-4-CUT within 0.987 and MAX-3-CUT within 0.9649. They also built near-extremal Ramanujan graphs of up to 163 nodes for average-case hardness results; checking the gadgets was sped up ~10,000×.
Key facts
- arXiv 2509.18057 'Reinforced Generation of Combinatorial Structures'
- MAX-4-CUT inapproximability 0.987; MAX-3-CUT 0.9649
- Correctness of the final theorems checked by standard (non-AI) verification
Science result
- Field
- computer-science / complexity theory / hardness of approximation
- Problem
- Inapproximability thresholds for MAX-k-CUT
- Result
- New NP-hardness of approximation bounds from AI-discovered gadget reductions.
- AI system
- AlphaEvolve
- Human role
- Human-led with AI tools: researchers framed the gadget search and proved the theorems
- Verification
- Preprint; gadgets verified by exhaustive computation
- Status
- confirmed
What happened
AlphaEvolve searched for finite combinatorial gadgets whose properties imply hardness theorems. Standard verification then turned the found objects into proofs.
Why it matters
AI-found objects became ingredients of rigorous complexity-theory theorems, not just numeric improvements.
Changelog
- 2026-09-29: created
Related events
Sources (2)
- paperReinforced Generation of Combinatorial Structures (arXiv 2509.18057)
- officialGoogle Research: AI as a research partner — advancing theoretical CS with AlphaEvolve
id: 2025-09-22-alphaevolve-hardness-of-approximation · updated 2026-09-29 · open in the interactive timeline