On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

A $μ$-constrained Boolean Max-CSP$(ψ)$ instance is a Boolean Max-CSP instance on predicate $ψ:\{0,1\}^r \to \{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 $(ψ)$ 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($ψ$) up to factor ${\sf Gap}_{\ell,μ}(ψ)/\log(1/μ)^2$ (ignoring factors depending on $r$) for any $\ell \geq \ell(μ,r)$. Here, ${\sf Gap}_{\ell,μ}(ψ)$ is the optimal integrality gap of $\ell$-round Lasserre relaxation for $μ$-constrained Max-CSP($ψ$) 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.