摘要：For every integer $k \ge 3$, we prove that there is a predicate $P$ on $k$ Boolean variables with $2^{\widetilde{O}(k^{1/3})}$ accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint $P$, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Håstad and Khot ( Theory of Computing, 2005) who showed that a predicate on $k$ variables with $2^{O(k^{1/2})}$ accepting assignments is approximation resistant on satisfiable instances
