{"id":"arxiv/2608.00333","url":"https://arxiv.org/abs/2608.00333","tags":["cs.CC","math.CO","math.PR","quant-ph"],"score":0,"title":"Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT","domain":"cs.CC","source":"arxiv","authors":["Steven Heilman"],"reviews":0,"subject":"cs.CC","summary":"Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $α_3+ε$ for every $ε>0$, where $α_3\\approx.83600811464$ is the approximation ratio of Frieze-Jerrum's polynomial-time algorithm from 1995. That is, we prove sharp hardness of approximation for MAX-3-CUT. This result resolves a conjecture of Khot-Kindler-Mossel-O'Donnell from 2004 by proving the three candidate Plurality is Stablest Conjecture for correlations in $[-1/2,2/5]$ and generalizes the Majority is Stablest Theorem of Mossel-O'Donnell-Oleszkiewicz [Annals of Math,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-31","reactions":{}}