--- id: "2025-09-22-alphaevolve-hardness-of-approximation" url: "https://postcutoff.com/e/2025-09-22-alphaevolve-hardness-of-approximation/" as_of: "2026-11-22T13:32:00+01:00" date: "2025-09-22" date_precision: day category: science importance: 2 confidence: medium status: [Result confirmed] verification: Preprint only sources: 2 editor: human editor human_review: null version: "2026-10-04" --- As of: 2026-11-22 13:32 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2025-09-22-alphaevolve-hardness-of-approximation/ # 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 ## 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. ## Your AI and this story - GPT-6.2 Astra (training cutoff May 2026): in its training data - Claude Opus 5.5 (training cutoff June 2026): in its training data - Gemini 4 Hydrogen (training cutoff March 2026): in its training data - Grok 4.7 (training cutoff May 2026): in its training data ## Sources 1. [Reinforced Generation of Combinatorial Structures (arXiv 2509.18057)](https://arxiv.org/abs/2509.18057) (arxiv.org, paper) 2. [Google Research: AI as a research partner — advancing theoretical CS with AlphaEvolve](https://research.google/blog/ai-as-a-research-partner-advancing-theoretical-computer-science-with-alphaevolve/) (research.google, official) ## Changes - 2026-09-29 (filed): Created ## Related - 2025-05-14: [AlphaEvolve: Gemini-powered agent discovers new algorithms](https://postcutoff.com/e/2025-05-14-alphaevolve/index.md)