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       : https://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).