Approximation Resistance by Disguising Biased Distributions
classification
💻 cs.CC
keywords
authoralgorithmapproximationbiasedcharikarconcludedisguisingdistributions
read the original 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$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.