Reinforced Generation of Combinatorial Structures: Hardness of Approximation

1 Introduction

• The authors improve lower bounds and analytical upper bounds for certifying MAX-CUT and MAX-IND-SET on sparse random graphs, achieving an almost tight resolution.The lower bounds improve on structures from [KY24], and the upper bounds improve on Hoffman’s classic spectral bounds; the bounds match to the second decimal place.Source: §1 · p. 3
• MAX-4-CUT hardness improves from 0.9883 to 0.987, while MAX-3-CUT gadget-based hardness improves from 0.9853 to 0.9649.The MAX-3-CUT result lies between custom-PCP results of 0.9696 [GS09] and 0.9411.Source: §1 · p. 3
• Metric TSP hardness improves from 117/116 to 111/110 using a new gadget-based reduction from standard Håstad PCPs [H˚as01].The reduction uses a single AI-derived technique to find and verify finite combinatorial structures.Source: §1 · p. 3
• AlphaEvolve iteratively evolves code that generates combinatorial structures, guided by an evaluation function and an LLM proposing revised code.The structures are finite, while lifting arguments embed the main results for every instance size n.Source: §1 · p. 3
• MAX-k-CUT gadget verification requires checking Ω(k^m) constraints, so the authors used AlphaEvolve to speed up the verifier by 10,000× for their final gadgets.The final gadgets contain m = 14 variables for k = 3 and m = 19 for k = 4; the speedup combines system-level improvements with branch-and-bound pruning.Source: §1 · p. 4
• The theorems do not rely on the fast verifiers being correct: the discovered gadgets were checked by brute force against all Ω(k^m) constraints.For sparse-graph certification, Ramanujan graphs and cut or independent-set witnesses could be efficiently checked, enabling verification of graphs with as many as 163 vertices.Source: §1 · p. 4

• AlphaEvolve searches for Ramanujan graphs with large cut or independent-set witnesses, strengthening certification lower bounds under the quiet-planting conjecture.The search scores graph-witness pairs and can verify Ramanujan status and witness validity efficiently.Source: §2 · pp. 5, 7
• σMC3 ≥17/36 (>0.472) and σIS4 ≥74/163 (>0.453) are conditional hardness bounds under Conjecture 2.1.The bounds are supported by AlphaEvolve constructions, including a witness on as many as 163 vertices for γIS4.Source: §2 · pp. 6–7
• Higher-order quadratic forms yield a linear program over labelings of a d-regular tree, improving the MAX-CUT upper bound over Hoffman’s L = 1 bound.The distribution models the local view of a cut at a random vertex; the LP is solved for small fixed L > 1.Source: §2 · p. 6
• 0.005: upper and lower bounds on σMC3 and σIS4 match within this absolute error, making Theorems 2.1 and 2.2 nearly optimal in those cases.The lower bounds are conditional on Conjecture 2.1.Source: §2 · p. 6
• The study focuses on d ∈ {3, 4}; for d = 3 MAX-CUT, AlphaEvolve recovered [KY24]’s γMC3 ≥17/18 bound but did not improve it.The authors expect similar improvements for reasonably small d > 4, except when d − 1 is an odd perfect square, where [BBK+21] already gives the optimal lower bound.Source: §2 · p. 7

3 Gadget based NP-Hardness for Approximating MAX-k-CUT

• 0.9649 + ε for MAX-3-CUT and 0.987 + ε for MAX-4-CUT are NP-hard approximation thresholds.The MAX-4-CUT bound improves on the prior 85/86 + ε result; the MAX-3-CUT result remains below the 16/17 + ε bound obtained using a custom Label Cover reduction.Source: §3 · pp. 9–10
• 55/57 + ε for MAX-3-CUT improves on earlier gadget-based results but does not beat 16/17 + ε; the reduction uses H˚astad’s classic PCP [H˚as01].The 16/17 + ε result uses a custom reduction from Label Cover.Source: §3 · pp. 9–10

3.1 Developing a Search Framework for Soundness and Completeness Guarantees

• The search framework reduces 3LIN(k) constraints to MAX-k-CUT gadgets, scores candidates by their implied inapproximability ratio, and adds global variables to break MAX-k-CUT’s symmetry.The framework uses AlphaEvolve to search for these reductions.Source: §3 · p. 8, §3.1 · p. 10
• MAX-4-CUT search explored gadgets with up to 19 variables and real-valued weights, which after scaling and rounding ranged from 1 to 1429.Evaluating a 19-variable gadget took about one second even with the optimized verifier.Source: §3.1 · p. 11

3.2 Faster Verification via AlphaEvolve to Explore Larger Gadgets

• For k = 4 at m = 19, the final verifier achieved a 10,000× speedup over a numba-accelerated brute-force verifier, using a more sequential branch-and-bound strategy and systems-level improvements.Source: §3.2 · p. 12

3.3 Comparison to other computational techniques

• The TSSW linear-program approach becomes doubly exponential in the number of satisfying assignments, while a mixed-integer program for a 14-variable gadget took 10 hours.The authors describe both approaches as computationally infeasible at the scale of these problems.Source: §3.3 · p. 12

• 111/110 − ε is the metric-TSP approximation threshold below which approximation is NP-hard, improving the prior 117/116 result.Source: §4 · p. 12
• The reduction starts from Hybrid-3LIN(2), a structured weighted CSP, and maps it to metric TSP through MWST.Each variable appears in exactly three equations, which may be 3LIN(2) constraints or binary linear constraints.Source: §4 · p. 12
• MWST represents metric TSP with minimum-weight spanning tours; the triangle inequality permits shortcutting repeated visits into a Hamiltonian cycle of no greater cost.Working on the sparse graph also lets the reduction assign weights locally.Source: §4 · pp. 12–13
• Each 3LIN(2) equation gadget encodes variable assignments through whether contact vertices share a tour with the shared central vertex.Source: §4 · p. 13
• The new gadget yields tour-collection weights of 10 for satisfying assignments and at least 11 for unsatisfying ones, versus 13 and 14 for the earlier gadget.This improves the resulting inapproximability ratio from 117/116 to 111/110.Source: §4 · p. 13
• The reduction modularizes soundness and completeness around parameters defined as optimization problems on equation gadgets, which may be useful independently.Source: §4 · p. 14

• Gadget soundness and completeness constraints can yield doubly exponential LPs or prohibitively many MIP constraints, limiting standard solvers even for modest gadgets.The TSP example has around 11! constraints for a 12-vertex equation gadget.Source: §5 · p. 16
• Standard SMT/MIP solvers failed to produce the gadgets, although human experts or highly customized computational verifiers could conceivably find them; asymmetry appears central to the TSP improvement.Source: §5 · p. 16
• For metric TSP, the proof logic had to be refactored by hand to make the problem amenable to AlphaEvolve.Source: §5 · p. 16
• The durability of AI-assisted results remains uncertain: some have been quickly matched or improved by humans, while others were already known to researchers.Source: §5 · p. 16
• Literature summaries can help non-specialists learn unfamiliar domains, but the authors had not obtained novel results by prompting an LLM for research plans or direct proofs.They anticipate that faster cross-disciplinary learning may foster scientific cross-pollination.Source: §5 · pp. 15–16
• They expect verification to remain a bottleneck and leave open whether directly prompting an LLM can replicate or surpass their results.Source: §5 · p. 16
• The authors suggest gadget-based reductions can be optimized beyond traditional methods, while beating AlphaEvolve may require non-gadget methods such as custom PCPs.Source: §5 · p. 16
• AlphaEvolve did not find a Hadamard matrix of order 668 despite fast candidate verification, and also failed to reproduce the known order-428 construction.Source: §5 · pp. 16–17

• The propose-test-refine process begins with a concrete finite-structure target, then uses AlphaEvolve to modify code snippets and a verifier to score generated candidates.The source and target problems may form parameterized families, while the gadgets sought here are finite structures.Source: A AlphaEvolve as a Framework for… · p. 22
• AlphaEvolve searches for code that generates high-scoring combinatorial structures, rather than directly searching the structures themselves.Source: A AlphaEvolve as a Framework for… · p. 22
• A verifier scores valid and invalid candidates, with the scoring function indicating how far an invalid structure lies from satisfying its constraints.The paper describes smooth scoring as changing gradually near constraint boundaries.Source: A AlphaEvolve as a Framework for… · pp. 22–23
• A genetic algorithm selects a diverse, high-scoring subset of prior code snippets to inform each new AlphaEvolve proposal.Source: A AlphaEvolve as a Framework for… · p. 22
• For MAX-k-CUT, AlphaEvolve accelerated verification by as much as 10,000×, while the correctness of the paper’s theorems does not depend on those faster verifiers.The discovered gadgets were checked with a brute-force algorithm.Source: A AlphaEvolve as a Framework for… · p. 23

• The witnesses include a 3-regular Ramanujan graph on 36 vertices and 4-regular Ramanujan graphs on 124 and 163 vertices.Source: §B.1 · p. 24
• 17/36 and 74/163 are witnessed independent-set fractions for 3- and 4-regular graphs, while the 4-regular cut witness gives 113/124.Source: §B.1 · p. 24

Spectral setting

• The bounds strengthen Hoffman’s classical bounds for graphs with λ∗(G) ≤2√(d−1)+ε.The proof also notes that its LP recovers Hoffman’s bound when L=1.Source: §B.2 · p. 25

LP construction

• The LP projects graph and cut information onto depth-L neighborhoods, using local consistency, root-label, spectral, and cut-objective constraints.Its objective is the cut fraction, and solving it over discretized α values bounds every cut in the specified graph class.Source: §B.2 · pp. 25–26

Computational efficiency

• The LP is made more tractable by identifying isomorphic labelings and discarding locally suboptimal labelings after preprocessing.Even the unoptimized d=3, L=4 formulation has 246 variables; the d=4, L=3 case has 11,880 variables and yields the same bound as the L=2 case.Source: §B.2 · p. 26

MAX-CUT bounds

• MC(G) ≤0.953 for G ∈Ω3,λ and MC(G) ≤0.916 for G ∈Ω4,λ, from solved LPs with L=4 and L=2, respectively.The programs use 4396 and 88 variables, respectively, with δ=0.0005.Source: §B.2 · p. 26

Independent-set bounds

• For MAX-Independent Set, the LP restricts support to tree labelings with no edge whose endpoints are both labeled 1, then seeks the largest feasible α.The supplied passage reports tractable program sizes but does not include the resulting bounds.Source: §B.2 · p. 27

Gadget reduction

• The reduction uses one i-gadget for each predicate P≡i 3,k, mapping that predicate to a MAX-k-CUT instance.Each gadget has three primary variables, k global variables, and auxiliary variables.Source: C Proofs of Theorems 3.1 and 3.2 · p. 27

Source hardness

• H˚astad’s theorem makes it NP-hard to distinguish nearly fully satisfiable 3LIN(k) instances from instances with at most about a 1/k satisfiable fraction [H˚as01].The source instance has m/k clauses for each of the k predicates.Source: C Proofs of Theorems 3.1 and 3.2 · p. 28

Completeness and soundness

• The gadget parameters determine completeness a and soundness b for the MAX-k-CUT instance, yielding the reduction’s approximation gap.The proof establishes the target cases by translating the source completeness and soundness cases.Source: C Proofs of Theorems 3.1 and 3.2 · p. 28

Completeness analysis

• For completeness, a nearly satisfying source assignment is extended with a fixed global assignment and a per-clause gadget witness.This gives at least (a−ε′)M satisfied target clauses for arbitrarily small ε′.Source: C Proofs of Theorems 3.1 and 3.2 · p. 28

Soundness analysis

• For soundness, global-variable symmetry is normalized and the source predicate frequencies are bounded to show no target assignment exceeds (b+ε′)M satisfied clauses.The normalized frequencies form a probability distribution, whose extremum is attained by concentrating on a predicate maximizing s1.Source: C Proofs of Theorems 3.1 and 3.2 · p. 29

Gadget representation

• The listed gadget construction includes weighted edge lists, where each tuple (a,b,w) represents w parallel inequality clauses between variables a and b.Some MAX-3-CUT gadgets are formed by reordering global variables, including the i=2 gadget’s reordering of variables 4, 5, and 6.Source: §C.1 · pp. 29–30

MAX-3-CUT gadgets

• For MAX-3-CUT, the i=0 gadget has c=s1=t=18 and s2=16; the i=1,2 gadgets have c=s1=48, s2=46, and 53 clauses.The gadgets’ parameters are used with the reduction theorem to derive Theorem 3.1.Source: §C.1 · p. 30

MAX-4-CUT gadgets

• The MAX-4-CUT gadgets are specified as i-gadgets with parameters c, s1, s2, and count, then combined with the reduction theorem for Theorem 3.2.The supplied passage does not provide the parameter values.Source: §C.1 · pp. 30–31

Hybrid-3LIN(2) hardness

• Theorem D.1 supplies a structured Hybrid-3LIN(2) instance that is NP-hard to distinguish between assignments satisfying all equality and inequality clauses and nearly all 3LIN(2) clauses, and assignments leaving at least (2/3 − ε)nk clauses unsatisfied.The instance combines parity clauses with two-variable equality and inequality clauses.Source: D Proof of the Hardness of… · pp. 32–33

Reduction construction

• A simple reduction shows that approximating MWSTf is equivalent to approximating MWST; the construction includes one central vertex alongside a vertex for each variable.Source: D Proof of the Hardness of… · pp. 31, 33

Completeness and soundness

• For any equation gadget H, completeness bounds tour cost by nk · (30 + 2 · c(H)/3) + 2(∆+ 2n) · w(H), while soundness turns a tour costing at most nk · (30 + 2 · s(H)/3) + ∆ into an assignment leaving at most 2∆ clauses unsatisfied.Here c(H) and s(H) are the gadget's completeness and soundness parameters.Source: D Proof of the Hardness of… · pp. 31, 33

Theorem D.2

• Theorem D.2 makes it NP-hard to distinguish MWSTf instances with tours of weight at most nk · (30 + 2 · c(H)/3) + 2(εnk + 2n) · w(H) from instances whose tours all weigh at least nk · (30 + 2 · s(H)/3) + nk · (1/3 − ε/2).The bounds follow from completeness and soundness lemmas for the reduction from the Hybrid-3LIN(2) problem in Theorem D.1.Source: D Proof of the Hardness of… · pp. 33–34

D Proof of the Hardness of Approximation for TSP

• The expected number of unsatisfied clauses in I is at most dch + dco + 2pch + 2r.Equality clauses contribute at most dch + dco, inequality clauses contribute pch, and the remaining unsatisfied 3LIN(2) clauses contribute r.Source: D Proof of the Hardness of… · p. 36
• w(T) ≥ nk · (30 + 2 · s(H)/3) + (dch + dco)/2 + pch + r.Here dch and dco count dishonest checker and contact vertices, pch counts specified violated inequality constraints, and r counts unsatisfied clauses whose variables are all honest.Source: D Proof of the Hardness of… · pp. 36–37
• A tour of weight at most nk · (30 + 2 · s(H)/3) + Δ yields an assignment leaving at most 2Δ clauses unsatisfied.The bound follows by combining the tour-weight and expected-unsatisfied-clause bounds; therefore, some assignment achieves it.Source: D Proof of the Hardness of… · pp. 36–37

D.2 Description of our gadget

• The gadget has four auxiliary vertices and is specified by weighted edge lists for its unforced and forced edges.Its vertex set is [3 + 1 + naux], with naux = 4.Source: §D.2 · p. 38
• Satisfying assignments admit tours of cost at most 10, while tours corresponding to unsatisfying assignments have weight at least 11.The gadget has c(H) = s(H) = 10 and maximum edge weight 2.Source: §D.2 · p. 38
• Metric TSP is NP-hard to approximate within 111/110 − ε for any ε > 0.The conclusion follows from the gadget result and the equivalence of MWST and metric TSP.Source: §D.2 · p. 38

D.3 Equation gadget for predicate x + y + z ≡0 (mod 2)

• The P≡0 clause setting is equivalent to the P≡1 setting under pointwise negation, but the assignment encoding is not symmetric under negation.This asymmetry requires formally different notions of soundness and completeness.Source: §D.3 · p. 38
• [CC20]’s gadget has s′(H) = c′(H) = 13 and yields metric TSP inapproximability of 117/116 − ε.Their gadget uses the modified soundness and completeness definitions for the P≡0 setting.Source: §D.3 · p. 38
• The alternative P≡0 gadget uses eight auxiliary vertices and is significantly more complicated than the P≡1-based gadget.The displayed Figure 8 equation gadget represents variables 1, 2, and 3.Source: §D.3 · pp. 38–39, Figure 8 · p. 39
• The P≡0 gadget achieves s′(H) = c′(H) = 10, providing an alternative route to the main result.The authors choose the less complicated P≡1-based gadget, which achieves s(H) = c(H) = 10.Source: §D.3 · p. 39