Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-040 | 17th April 2012 13:37

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

TR12-040
Authors: Sangxia Huang
Publication: 17th April 2012 17:42
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.