Theory of Computing
-------------------
Title     : SDP Gaps from Pairwise Independence
Authors   : Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani
Volume    : 8
Number    : 12
Pages     : 269-289
URL       : https://theoryofcomputing.org/articles/v008a012

Abstract
--------

We consider the problem of approximating fixed-predicate constraint
satisfaction problems (MAX k-CSP_q (P)), where the variables take
values from [q]={0,1,...,q-1}, and each constraint is on k
variables and is defined by a fixed k-ary predicate P.  Familiar
problems like MAX 3-SAT and MAX-CUT belong to this category.
Austrin and Mossel recently identified a general class of
predicates P for which MAX k-CSP_q (P) is hard to approximate. They
study predicates P:[q]^k -> {0,1} such that the set of assignments
accepted by P contains the support of a balanced pairwise
independent distribution over the domain of the inputs.  We refer
to such predicates as promising. Austrin and Mossel show that for
any promising predicate P, the problem MAX k-CSP_q (P) is
Unique-Games hard to approximate better than the trivial
approximation obtained by a random assignment.

We give an unconditional analogue of this result in a restricted
model of computation.  We consider the hierarchy of semidefinite
relaxations of MAX k-CSP_q (P) obtained by augmenting the canonical
semidefinite relaxation with the Sherali-Adams hierarchy. We show
that for any promising predicate P, the integrality gap remains
the same as the approximation ratio achieved by a random
assignment, even after Omega(n) levels of this hierarchy.

We also introduce a new general set of techniques to define
consistent "local distributions" over partial assignments to
variables in the problem. Defining such distributions has often
been the crux of proving lower bounds on integrality gaps for
hierarchies like the ones we consider.