Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory

• URL: http://arxiv.org/abs/2509.18057v4
• Date: Mon, 06 Oct 2025 17:09:53 GMT
• Title: Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory
• Abstract summary: We explore whether techniques from AI can help discover new structures that improve on known limits on efficient algorithms.<n>Specifically, we use AlphaEvolve to study two settings: a) Average-case hardness for MAX-CUT and MAX-Independent Set.<n>Our improved lower bounds are obtained by constructing nearly extremal Ramanujan graphs on as many as $163$ nodes.
• Score: 3.359365297148466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We explore whether techniques from AI can help discover new combinatorial structures that improve on known limits on efficient algorithms. Specifically, we use AlphaEvolve (an LLM coding agent) to study two settings: a) Average-case hardness for MAX-CUT and MAX-Independent Set: 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$ nodes, using AlphaEvolve. Additionally, via analytical arguments we strengthen the upper bounds to settle the computational hardness of these questions up to an error in the third decimal place. b) Worst-case Hardness of Approximation for MAX-k-CUT: We obtain new inapproximability results, proving that it is NP-hard to approximate MAX-4-CUT and MAX-3-CUT 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 improving the SOTA of $16/17$ that relies on a custom PCP, rather than a gadget reduction from "standard" H{\aa}stad-style PCPs. A key technical challenge we faced: verifying a candidate construction produced by AlphaEvolve is costly (often requiring exponential time). In both settings above, our results were enabled by using AlphaEvolve itself to evolve the verification procedure to be faster (sometimes by $10,000\times$). We conclude with a discussion of norms by which to assess the assistance from AI in developing proofs.

Related papers

• Bilevel Optimization over Saddle Points of Zero-Sum Markov Games [80.76110725150467]
  Reinforcement learning (RL) often has a hierarchical structure, where an upper-level (UL) learner selects model parameters and a lower-level (LL) decision-making process responds.<n>Most existing bilevel RL methods assume a single-policy LL Markov decision process (MDP), and therefore fail to capture competitive structures arising in applications such as incentive design.<n>We study bilevel optimization problems in which the LL problem is a regularized min-max zero-sum Markov game and the UL objective is optimized through the saddle-point equilibrium induced by the LL game.
  arXiv  Detail & Related papers  (2026-05-26T07:38:24Z)
• QUASAR: An Evolutionary Algorithm to Accelerate High-Dimensional Optimization [0.0]
  This paper introduces Quasi-Adaptive Search with Asymptotic Reinitialization (QUASAR)<n>QUASAR is an evolutionary algorithm to accelerate convergence in complex, non-differentiable problems afflicted by the curse of dimensionality.
  arXiv  Detail & Related papers  (2025-11-17T19:02:31Z)
• Quantum Max-Cut is NP hard to approximate [0.06768558752130309]
  We prove that it is NP-hard to compute a constant multiplicative approximation to the QUANTUM MAX-CUT problem on an unweighted graph of constant bounded degree.
  arXiv  Detail & Related papers  (2025-10-09T09:32:08Z)
• Learning-Augmented Algorithms for Boolean Satisfiability [7.642039348547126]
  We study the classic Boolean satisfiability (SAT) decision and optimization problems using two forms of advice.<n>Subset advice provides a random $epsilon$ fraction of the variables from an optimal assignment, whereas label advice" provides noisy predictions for all variables in an optimal assignment.<n>For the optimization problem, we show how to incorporate subset advice in a black-box fashion with any $alpha$-approximation algorithm.
  arXiv  Detail & Related papers  (2025-05-09T15:54:34Z)
• Learning the closest product state [12.421740476704759]
  We study the problem of finding a (pure) product state with optimal fidelity to an unknown $n$-qubit quantum state $rho$, given copies of $rho$.<n>We give an algorithm which finds a product fidelity $varepsilon$-close to optimal, using $N = ntextpoly (1/varepsilon)$ copies of $rho$ and $textpoly(N)$ classical overhead.
  arXiv  Detail & Related papers  (2024-11-06T22:08:08Z)
• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
  The minimax problems arise throughout machine learning applications, ranging from machine learning training to large-scale learning. We propose a class of algorithms for non minimax problems (emphi) that reduce complexity to $varepsilon-6)$. We prove that FedSGDA-M has the best sample complexity of $O(kappa2-3)$ and the best-known communication of $O(kappa2-3)$.
  arXiv  Detail & Related papers  (2023-10-05T15:48:41Z)
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
  We present an explicit algorithm to evaluate the performance of QAOA on MAX-CUT applied to random Erdos-Renyi graphs of expected degree $d$. This analysis yields an explicit mapping between QAOA parameters for MAX-CUT on Erdos-Renyi graphs, and the Sherrington-Kirkpatrick model.
  arXiv  Detail & Related papers  (2021-10-20T17:58:53Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  We show that a modified greedy algorithm can achieve an approximation factor of $0.305$. We derive a data-dependent upper bound on the optimum. It can also be used to significantly improve the efficiency of such algorithms as branch and bound.
  arXiv  Detail & Related papers  (2020-08-12T15:40:21Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  In this paper, we denote the non-strongly setting on the magnitude of a gradient-free minimax optimization problem. We show that a novel zeroth-order variance reduced descent algorithm achieves the best known query complexity.
  arXiv  Detail & Related papers  (2020-06-16T17:55:46Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  Zeroth-order (a.k.a, derivative-free) methods are a class of effective optimization methods for solving machine learning problems. In this paper, we propose a class faster faster zerothorder alternating gradient method multipliers (MMADMM) to solve the non finitesum problems. We show that ZOMMAD methods can achieve a lower function $O(frac13nfrac1)$ for finding an $epsilon$-stationary point. At the same time, we propose a class faster zerothorder online ADM methods (M
  arXiv  Detail & Related papers  (2019-07-30T02:21:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.