pdf icon
Volume 10 (2014) Article 14 pp. 359-388
Approximation Resistance on Satisfiable Instances for Sparse Predicates
Received: May 13, 2013
Revised: January 18, 2014
Published: October 15, 2014
Download article from ToC site:
[PDF (335K)] [PS (1426K)] [Source ZIP]
Keywords: Max-CSP, probabilistically checkable proofs, approximation resistance, satisfiable instance
ACM Classification: F.2.2, F.1.3, G.1.6
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

For every integer $k \ge 3$, we prove that there is a predicate $P$ on $k$ Boolean variables with $2^{\widetilde{O}(k^{1/3})}$ accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint $P$, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Håstad and Khot (Theory of Computing, 2005) who showed that a predicate on $k$ variables with $2^{O(k^{1/2})}$ accepting assignments is approximation resistant on satisfiable instances.

Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Siu On Chan (STOC 2013). We also use techniques from Cenny Wenner (Theory of Computing, 2013) to construct PCPs with perfect completeness without relying on the $d$-to-1 Conjecture.

A conference version of this paper appeared in the Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 2013.