Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity
2012 (English)Report (Other academic)
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 MaxCSP(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 5/8 + epsilon for any epsilon > 0 based on Khot’s d-to-1 Conjecture, where NTW is the “Not Two” predicate of size 3.
Place, publisher, year, edition, pages
2012. , 21 p.
, Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092 ; 40
pcp, approximation, d-to-1, perfect completeness
IdentifiersURN: urn:nbn:se:kth:diva-108165OAI: oai:DiVA.org:kth-108165DiVA: diva2:579115
FunderEU, European Research Council, 6853
QC 201301092013-01-092012-12-192013-01-09Bibliographically approved