__
TR12-040 | 17th April 2012 13:37
__

#### Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity

**Abstract:**
In this paper, we study the approximability of Max CSP($P$) where $P$ is a Boolean predicate. We prove that assuming Khot's $d$-to-1 Conjecture, if the set of accepting inputs of $P$ strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate Max CSP($P$) better than the simple random assignment algorithm even on satisfiable instances. This is a generalization of a work by O'Donnell and Wu which proved that it is NP-hard to approximate satisfiable instances of Max CSP(NTW) beyond $\frac{5}{8}+\varepsilon$ for any $\varepsilon>0$ based on Khot's $d$-to-1 Conjecture, where NTW is the ``Not Two'' predicate of size 3.