Sharp Hardness for MAX-3-CUT
Assuming the Unique Games Conjecture, it is NP-hard to approximate MAX-3-CUT better than the Frieze-Jerrum semidefinite program does, and similarly for Quantum MAX-CUT: the sharpness question in the Khot-Kindler-Mossel-O'Donnell line, connected to the Plurality is Stablest problem.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-assisted
- Method
- Argument
- Field
- Hardness of approximation
- Posed by
- S. Khot, G. Kindler, E. Mossel, R. O'Donnell
- Year posed
- 2004
- Years open
- 22y
- Solved
- 2026-07-31
- Model
- ChatGPT 5.6
- Vendor
- OpenAI
- Collaborators
- Steven Heilman
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 25 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
ChatGPT 5.6 assisted in the preparation of the manuscript, including producing the spectral certificates in Propositions 4.1 and 4.4 and Lemmas 9.3 and A.4 - proof components, not prose.