Approximation Resistance by Disguising Biased Distributions

Abstract

In this short note, the author shows that the gap problem of some 3-XOR is NP-hard and can be solved by running Charikar\&Wirth's SDP algorithm for two rounds. To conclude, the author proves that $P=NP$.

6 pages, short note

References in corpus (1)

• Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion