Hardness of Approximation for Semialgebraic CSPs: Every Geometric Semialgebraic CSP is Approximation ResistantResearch Paper
A constraint satisfaction problem (CSP) is approximation resistant if no polynomial-time algorithm beats a trivial baseline by a constant: on near-satisfiable instances, finding an assignment better than the baseline by any fixed is NP-hard. Håstad proved this for 3SAT with the uniformly random assignment as the baseline (Håstad 2001). Later work…