Maj-Stablest + UGC implies:
(From Khot 2002): (1-e,1-O(e1/2)) hardness for
MAX-2-LIN (mod 2) and MAX-2-SAT.
From (Khot-Kindler-M-ODonnell 2005):
Goemans-Williamson algorithm achieves tight approximation factor (0.878
) for MAX-CUT.
8 e > 0 9 q(e) such that
MAX-2-LIN(mod q) has (1-e,e) hardness.
MAX-q-CUT has (1-1/q+o(1/q)) hardness factor (matches Frieze & Jerrum semi-definite
algorithm).