On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
Suprovat Ghoshal, Euiwoong Lee · 2023
A $\mu$-constrained Boolean MAX-CSP $(\psi)$ instance is a Boolean Max-CSP instance on predicate $\psi:\{0,1\}^{r} \rightarrow\{0,1\}$ where the objective is to find a labeling of relative weight exactly $\mu$ 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 $\operatorname{Max}-\operatorname{CSP}(\psi)$ to its $\mu$-dependent approximation curve. Formally, assuming the Small-Set Expansion Hypothesis, we show that it is NP-hard to approximate $\mu$-constrained instances of $\operatorname{MAX}-\operatorname{CSP}(\psi)$ up to factor $\operatorname{Gap}_{\ell, \mu}(\psi) / \log (1 / \mu)^{2}$ (ignoring factors depending on r) for any $\ell \geq \ell(\mu, r)$. Here, $\operatorname{Gap}_{\ell, \mu}(\psi)$ is the optimal integrality gap of $\ell$-round Lasserre relaxation for $\mu$-constrained $\operatorname{MAX}-\operatorname{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.