Abstract:
We study the approximability of predicates on $k$ variables from a domain $[q]$, and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate $P$ is approximation resistant if there exists a balanced pairwise independent distribution over $[q]^k$ whose support is contained in the set of satisfying assignments to $P$. Using constructions of pairwise indepenent distributions this result implies that: For general $k \ge 3$ and $q \ge 2$, the Max $k$-CSP$_q$ problem is UG-hard to approximate within $q^{\lceil \log_2 k +1 \rceil - k} + \epsilon$. For $k \geq 3$ and $q$ prime power, the hardness ratio is improved to $kq(q-1)/q^k + \epsilon$. For the special case of $q = 2$, i.e., boolean variables, we can sharpen this bound to $(k + O(k^{0.525}))/2^k + \epsilon$, improving upon the best previous bound of $2k/{2^k} + \epsilon$ (Samorodnitsky and Trevisan, STOC'06) by essentially a factor $2$. Finally, for $q=2$, assuming that the famous Hadamard Conjecture is true, this can be improved even further, and the $O(k^{0.525})$ term can be replaced by the constant $4$.