Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR12-145 | 31st October 2012 14:12

Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four


Authors: Cenny Wenner
Publication: 7th November 2012 13:40
Downloads: 824


HÃ¥stad established that any predicate $P \subseteq \{0,1\}^m$ 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 $\mathcal{P} \neq \mathcal{NP}$, the same approximation-resistance result for predicates of width four or greater.

ISSN 1433-8092 | Imprint