A predicate f:\{-1,1\}^k \mapsto \{0,1\} with \rho(f) = \frac{|f^{-1}(1)|}{2^k} is called {\it approximation resistant} if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment that satisfies at least \rho(f)+\Omega(1) fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

For a predicate f:\{-1,1\}^k \mapsto \{0,1\} with \rho(f) = \frac{|f^{-1}(1)|}{2^k}, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP(f), it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range [\rho(f)-\Omega(1), \rho(f)+\Omega(1)].

We present a characterization of ... more >>>

This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>>

A boolean predicate f:\{0,1\}^k\to\{0,1\} is said to be {\em somewhat approximation resistant} if for some constant \tau > \frac{|f^{-1}(1)|}{2^k}, given a \tau-satisfiable instance of the MAX-k-CSP(f) problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let \tau(f) denote ... more >>>

We consider the complexity of LS_+ refutations of unsatisfiable instances of Constraint Satisfaction Problems (CSPs) when the underlying predicate supports a pairwise independent distribution on its satisfying assignments. This is the most general condition on the predicates under which the corresponding MAX-CSP problem is known to be approximation resistant.

We ... more >>>

Lov\'{a}sz and Schrijver introduced several lift and project methods for 0-1 integer programs, now collectively known as Lov\'{a}sz-Schrijver (LS) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the LS and LS_+ hierarchies. In this paper we investigate rank bounds in the ... more >>>