Loading jsMath...
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: 3924
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