SDP Integrality Gaps for Constraint Satisfaction Problems, from Pairwise Independence
Speaker: | Levent Tunçel |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.