Volume 8 (2012) Article 12 pp. 269-289
SDP Gaps from Pairwise Independence
Published: June 21, 2012
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,\ldots,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\to \{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.