Metraipolis › archive › dc_ce2a2e2d6693

Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT — arXiv:2608.00333

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.00333
License (as archived)
CC0-1.0
Archived
2026-10-19T09:07:05.643Z
SHA-256 of the archived text
9dcdc689460edbd28824ed0643aa143379a47be2b9be63a2c71dd08d0e345a3d
Stable URL of this page
https://metraipolis.com/documento/dc_ce2a2e2d6693

How to cite

Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT — arXiv:2608.00333 — arXiv (en), https://arxiv.org/abs/2608.00333 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ce2a2e2d6693 (Metraipolis archive dc_ce2a2e2d6693, sha256 9dcdc689460edbd28824ed0643aa143379a47be2b9be63a2c71dd08d0e345a3d)
BibTeX
@misc{dcce2a2e2d6693,
  title = {Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT — arXiv:2608.00333},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.00333},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ce2a2e2d6693; sha256 9dcdc689460edbd28824ed0643aa143379a47be2b9be63a2c71dd08d0e345a3d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.00333. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $\alpha_3+\epsilon$ for every $\epsilon>0$, where $\alpha_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, 2010]. With a similar strategy we prove: assuming the Unique Games Conjecture, it is NP-hard to approximate the product-state value of Quantum MAX-CUT within a multiplicative factor of $\alpha_{\rm BOV}+\epsilon$ for every $\epsilon>0$, where $\alpha_{\rm BOV}\approx 0.9563372685$ is the approximation ratio of the Briët-de Oliveira Filho-Vallentin algorithm. This sharp hardness result completes the conjectured hardness of Hwang-Neeman-Parekh-Thompson-Wright from 2021 by proving their $S^{k-1}$-valued Borell inequality for correlations in $[-.5843,.5843]$ for all $k\geq3$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.PR).
Categorie arXiv: Computational Complexity (cs.CC) ; Combinatorics (math.CO); Probability (math.PR); Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2608.00333 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:04:32.186Z dalla pagina https://arxiv.org/catchup/math.PR/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).