ECCC-Report TR12-105https://eccc.weizmann.ac.il/report/2012/105Comments and Revisions published for TR12-105en-usFri, 24 Aug 2012 08:52:28 +0300
Paper TR12-105
| $LS_+$ Lower Bounds from Pairwise Independence |
Pratik Worah,
Madhur Tulsiani
https://eccc.weizmann.ac.il/report/2012/105We 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 $\Omega(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 $\Omega(n)$. We also show the stronger result that refutations for such instances in the \emph{static} LS$_+$ proof system requires size $\exp(\Omega(n))$.Fri, 24 Aug 2012 08:52:28 +0300https://eccc.weizmann.ac.il/report/2012/105