A characterization of strong approximation resistance
Subhash Khot, Madhur Tulsiani, Pratik Worah · 2014
For a predicate f: {-1, 1}k ↦ {0, 1} with ρ(f) = |f-1(1)|/2k, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range [ρ(f) - Ω(1), ρ(f) + Ω(1)].