Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity
Sangxia Huang · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2012
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.