Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs

Approximation Resistance on Satisfiable Instances for Predicates with Few Accepting Inputs

Sangxia Huang

For every integer
,
we prove that there is a predicate
on
Boolean variables with
accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint
,
we cannot achieve better approximation ratio than simply picking random assignments.
This improves the best previously known result by Håstad and Khot where the predicate has
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. We also use techniques from Wenner to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture.