H?stad established that any predicate P01m containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang who showed the threshold result that if a predicate strictly contains parity of width at least three, then it is approximation resistant also for satisfiable instances, assuming the d-to-1 Conjecture. We extend modern hardness-of-approximation techniques by Mossel et al. to projection games, eliminating dependencies on the degree of projections via Smooth Label Cover, and prove, subject only to = , the same approximation-resistance result for predicates of width four or greater.
展开▼
