SDP Integrality Gaps for Constraint Satisfaction Problems, from Pairwise Independence
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by P contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on n variables cannot be approximated better than the trivial (random) approximation, even after augmenting the natural semidefi nite relaxation with Omega(n) levels of the Sherali-Adams hierarchy. It was recently shown that under the Unique Game Conjecture, CSPs for predicates satisfying this condition cannot be approximated better than the trivial approximation. Our results can be viewed as an unconditional analogue of this result in a restricted computational model. We also introduce a new generalization of techniques to define consistent local distributions over partial assignments to variables in the problem, which is often the crux of proving lower bounds for such hierarchies.
This is joint work with Siavosh Benabbas, Avner Magen and Madhur Tulsiani.
200 University Avenue West
Waterloo, ON N2L 3G1