Theory of Computing
-------------------
Title : Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
Authors : Cenny Wenner
Volume : 9
Number : 23
Pages : 703-757
URL : http://www.theoryofcomputing.org/articles/v009a023
Abstract
--------
Hastad established that any predicate $P \subseteq \{0,1\}^m$
containing Parity of width at least three is approximation resistant
for almost-satisfiable instances . In comparison to for example the
approximation hardness of 3SAT, this general result however left open
the hardness of perfectly-satisfiable instances. This limitation was
addressed by O'Donnell and Wu, and subsequently generalized by Huang,
to show the threshold result that predicates _strictly_ containing
Parity of width at least three are approximation resistant also for
perfectly-satisfiable instances, assuming the $d$-to-1 Conjecture.
We extend modern hardness-of-approximation techniques by Mossel et
al., eliminating the dependency on projection degrees for a special
case of decoupling/invariance and -- when reducing from
_Smooth Label Cover_ -- the dependency on projection
degrees for noise introduction. Tools in hand, we prove the same
approximation-resistance result for predicates of width at least four,
subject only to P \neq NP.
A preliminary version of this paper appeared in the International
Workshop on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX'12).