Tutte seminar - Costis Georgiou

SDP Integrality Gaps for Constraint Satisfaction Problems, from Pairwise Independence

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.