Volume 8 (2012)
Article 12 pp. 269-289
SDP Gaps from Pairwise Independence
Received: August 8, 2011
Published: June 21, 2012
Keywords: semidefinite and linear programming hierarchies, integrality gaps, constraint satisfaction
ACM Classification: F.2.2, F.1.3, G.1.6, F.2.3
AMS Classification: 68Q17, 68Q25, 68W20, 90C59
Abstract:
[Plain Text Version]
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.
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.