Three-candidate Plurality is Stablest hardness consequence for MAX-3-CUT

Assume the Unique Games Conjecture and the three-candidate Plurality is Stablest Conjecture. Let α3\alpha_{3} denote the relevant MAX-3-CUT approximation threshold.

Sharp hardness consequence. For every ε>0\varepsilon>0, it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of α3+ε\alpha_{3}+\varepsilon.

This is the stated reduction from the Unique Games Conjecture and Plurality is Stablest to sharp MAX-3-CUT hardness. It is a conditional complexity-theoretic consequence rather than an independent mathematical conjecture; the source gives no resolution of the assumed conjectures.

Sources & referencesView supporting material

Primary source

Steven Heilman, “Three Candidate Plurality is Stablest for Correlations at most 1/10”, arXiv:2306.03312 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.