ECCC-Report TR12-040https://eccc.weizmann.ac.il/report/2012/040Comments and Revisions published for TR12-040en-usTue, 17 Apr 2012 17:42:18 +0300
Paper TR12-040
| Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity |
Sangxia Huang
https://eccc.weizmann.ac.il/report/2012/040In 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.Tue, 17 Apr 2012 17:42:18 +0300https://eccc.weizmann.ac.il/report/2012/040