Approximation Resistant Predicates from Pairwise Independence

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 independent distributions this result implies that ldr For general kges3 and qges2, the MAX k-CSP_q problem is UG-hard to approximate within O(kq²)/q^k+isin. ldr For the special case of q=2, i.e., boolean variables, we can sharpen this bound to (k+O(k^0.525))/2^k+isin, improving upon the best previous bound of2k/2^k+isin (Samorodnitsky and Trevisan, STOC'06) by essentially a factor 2. ldr Finally, again 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.