On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

A μ-constrained Boolean Max-CSP(psi) instance is a Boolean Max-CSP instance on predicate psi:0,1r → 0,1 where the objective is to find a labeling of relative weight exactly μ that maximizes the fraction of satisfied constraints. In this work, we study the approximability of constrained Boolean Max-CSPs via SDP hierarchies by relating the integrality gap of Max-CSP (psi) to its μ-dependent approximation curve. Formally, assuming the Small-Set Expansion Hypothesis, we show that it is NP-hard to approximate μ-constrained instances of Max-CSP(psi) up to factor sf Gapℓ,μ(psi)/log(1/μ)2 (ignoring factors depending on r) for any ℓ ≥ ℓ(μ,r). Here, sf Gapℓ,μ(psi) is the optimal integrality gap of ℓ-round Lasserre relaxation for μ-constrained Max-CSP(psi) instances. Our results are derived by combining the framework of Raghavendra [STOC 2008] along with more recent advances in rounding Lasserre relaxations and reductions from the Small-Set Expansion (SSE) problem. A crucial component of our reduction is a novel way of composing generic bias-dependent dictatorship tests with SSE, which could be of independent interest.