Approximation Resistance On Satisfiable Instances For Predicates With Few Accepting Inputs

We prove that for all integer k >= 3, there is a predicate P on k Boolean variables with 2 ((O) over tilde) (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 (a) over circle stad and Khot where the predicate has 2(O)(k(1/2)) accepting assignments.Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Chan [5]. We also use techniques from Wenner [32] to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture.