LS+ Lower Bounds from Pairwise Independence

摘要

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 show that for random instances of such CSPs on n variables, even after (n) rounds of the LS+ hierarchy, the integrality gap remains equal to the approximation ratio achieved by a random assignment. In particular, this also shows that LS+ refutations for such instances require rank (n). We also show the stronger result that refutations for such instances in the emph{static} LS+ proof system requires size exp((n)).