Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
2012 (English)In: Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
Approximation Resistance, correlations, d-to-1 conjecture, Invariance, Perfect Completeness, Smooth Label cover
IdentifiersURN: urn:nbn:se:kth:diva-113213OAI: oai:DiVA.org:kth-113213DiVA: diva2:587576
QC 201305022013-01-142013-01-142014-09-29Bibliographically approved