Title: The Complexity of Somewhat Approximation Resistant Predicates

Abstract:

For a Boolean predicate f on k variables, let \rho(f) be the probability that a constraint of the form f(x_1,...,x_k) is satisfied by a random assignment. A predicate f is called "somewhat approximation resistant" if for some constant \tau > \rho(f), given a \tau-satisfiable instance of the Max-k-CSP(f) problem, it is NP-hard to find an assignment that strictly beats the naive algorithm that outputs a uniformly random assignment.

Let \tau(f) denote the supremum over all \tau for which the above holds. It is known that a predicate is somewhat approximation resistant precisely when its Fourier degree is at least 3. For such predicates, we give a characterization of the "hardness gap" (\tau(f) -\rho(f)) up to a factor of O(k^5). We also give a similar characterization of the integrality gap for the natural SDP relaxation of Max-k-CSP after \Omega(n) rounds of the Lasserre hierarchy.

Joint work with Subhash Khot and Pratik Worah.