Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-040 | 17th April 2012 13:37

Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity

RSS-Feed




TR12-040
Authors: Sangxia Huang
Publication: 17th April 2012 17:42
Downloads: 3658
Keywords: 


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.



ISSN 1433-8092 | Imprint