{"id":"openai-math/A-Direct-Proof-of-Optimal-Max-Cut-Hardness","pdf":"https://github.com/openai/math/blob/main/preprints/A-Direct-Proof-of-Optimal-Max-Cut-Hardness-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-Direct-Proof-of-Optimal-Max-Cut-Hardness-September-23-2026","tags":["computational-complexity","approximation-algorithms","max-cut"],"score":0,"title":"A Direct Proof of Optimal Max-Cut Hardness","domain":"Theoretical computer science","family":"102","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"We prove that approximating Max-Cut on simple unweighted graphs within any fixed factor greater than the Goemans–Williamson constant is NP-hard.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{},"formalized":true,"family_title":"The Unique Games Conjecture and optimal approximation thresholds"}