SDP gaps and UGC-hardness for MAXCUTGAIN.

Subhash Khot, Ryan O'Donnell

Browse the full FOCS paper archive.