Volume 9 (2013) Article 23 pp. 703-757
APPROX-RANDOM 2012 Special Issue
Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
Revised: June 8, 2013
Published: September 13, 2013
Keywords: Boolean functions, hardness of approximation, inapproximability, constraint satisfaction, Fourier analysis, approximation resistance, dictatorship test, label cover, smooth label cover, correlation bounds, perfect completeness, invariance, $d$-to-$1$ games
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. 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.