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 >>>

Over the last twenty years, an exciting interplay has emerged between proof systems and algorithms. Some natural families of algorithms can be viewed as a generic translation from a proof that a solution exists into an algorithm for finding the solution itself. This connection has perhaps been the most consequential ... more >>>