Approximation Resistant Predicates from Pairwise Independence

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 2 )/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.