Three-candidate Plurality is Stablest hardness consequence for MAX-3-CUT
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 denote the relevant MAX-3-CUT approximation threshold.
Sharp hardness consequence. For every , it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.