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
Received: October 31, 2012
Revised: June 8, 2013
Published: September 13, 2013
Download article from ToC site:
[PDF (476K)]    [PS (2392K)]    [PS.GZ (570K)]
[Source ZIP]
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
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

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.

A preliminary version of this paper appeared in the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'12).