Published: June 21, 2012

**Keywords:**semidefinite and linear programming hierarchies, integrality gaps, constraint satisfaction

**Categories:**complexity theory, lower bounds, linear programming, semidefinite programming, integrality gap, SDP gap, 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
_{$q$}($P$)),_{$q$}($P$)*promising*. Austrin and Mossel show that for
any promising predicate $P$, the problem
_{$q$}($P$)

We give an unconditional analogue of this result in a restricted
model of computation. We consider the hierarchy of semidefinite
relaxations of
_{$q$}($P$)

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.