|
Friday, Dec 10, 2010 |
|
|
|
|
SDP Integrality Gaps for Constraint Satisfaction Problems, from Pairwise Independence |
|
|
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. |