Theory of Computing
-------------------
Title     : Approximation Resistance on Satisfiable Instances for Sparse Predicates
Authors   : Sangxia Huang
Volume    : 10
Number    : 14
Pages     : 359-388
URL       : https://theoryofcomputing.org/articles/v010a014

Abstract
--------

For every integer $k \ge 3$, we prove that there is a predicate $P$
on $k$ Boolean variables with $2^{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 Hastad 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.