{"ID":5438654,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T05:54:49.125664311Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31182","arxiv_id":"2606.31182","title":"AI-Assisted Discovery of Convex Relaxations via Dual Agents","abstract":"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 \\citet{tao2025alphaevolve} - the first autocorrelation inequality ($C_{6.2}$) and the Erdős minimum-overlap constant ($C_{6.5}$) - we improve the certified lower bounds from $1.28$ to $1.2937$ and from $0.379005$ to $0.37912$, respectively.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2606.31182","url_pdf":"https://arxiv.org/pdf/2606.31182v1","authors":"[\"Sungyoon Kim\",\"Mert Pilanci\"]","published":"2026-06-30T06:10:25Z","proceeding":"cs.AI","tasks":"[\"cs.AI\"]","methods":"[\"Large Language Model\"]","has_code":false}