# AI-Assisted Discovery of Convex Relaxations via Dual Agents

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 17 of its 52 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

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

- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Learning to Discover at Test Time](https://mlsanity.com/paper/2601.16175/) (2026)
- [Winning Gold at IMO 2025 with a Model-Agnostic Verification-and-Refinement Pipeline](https://mlsanity.com/paper/2507.15855/) (2025)
- [A Self-Improving Coding Agent](https://mlsanity.com/paper/2504.15228/) (2025)
- [Mathematical exploration and discovery at scale](https://mlsanity.com/paper/2511.02864/) (2025)
- [ThetaEvolve: Test-time Learning on Open Problems](https://mlsanity.com/paper/2511.23473/) (2025)
- [LiveCodeBench Pro: How Do Olympiad Medalists Judge LLMs in Competitive Programming?](https://mlsanity.com/paper/2506.11928/) (2025)
- [Early science acceleration experiments with GPT-5](https://mlsanity.com/paper/2511.16072/) (2025)
- [APOLLO: Automated LLM and Lean Collaboration for Advanced Formal Reasoning](https://mlsanity.com/paper/2505.05758/) (2025)
- [First Proof](https://mlsanity.com/paper/2602.05192/) (2026)
- [Advancing Mathematics Research with AI-Driven Formal Proof Search](https://mlsanity.com/paper/2605.22763/) (2026)
- [Structured Scaling of AI Discovery Across Diverse Scientific Domains](https://mlsanity.com/paper/2604.19341/) (2026)
- [130k Lines of Formal Topology in Two Weeks: Simple and Cheap Autoformalization for Everyone?](https://mlsanity.com/paper/2601.03298/) (2026)
- [SITA: A Framework for Structure-to-Instance Theorem Autoformalization](https://mlsanity.com/paper/2511.10356/) (2025)

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

- [Autonomous Mathematical Discovery in an Open-World Multi-Agent Environment](https://mlsanity.com/paper/2608.23691/) (2026)
- [Learning to Design Convex Relaxations for Nonconvex Optimization](https://mlsanity.com/paper/2610.16948/) (2026)

## Abstract (arXiv)

Recent work shows that LLM agents can improve sharp-constant inequalities by searching for extremal constructions, which yield upper bounds. We address the complementary side: a lower bound holds for every admissible function and follows from a convex relaxation of the nonconvex problem, with tighter relaxations giving stronger bounds. We instantiate the autoresearch paradigm to discover such relaxations: a coding agent proposes valid tightening constraints, a theory agent verifies each one and searches for counterexamples, and every reported bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. On two optimization constants studied by citettao2025alphaevolve - the first autocorrelation inequality (C6.2) and the ErdHos minimum-overlap constant (C6.5) - we improve the certified lower bounds from 1.28 to 1.2937 and from 0.379005 to 0.37912, respectively.