On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

Abstract

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

73 Pages