# On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

arXiv: https://arxiv.org/abs/2308.09667 · HTML: https://mlsanity.com/paper/2308.09667/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Aug 2023.

## Built on by (most cited first, 1 of 1)

- [Algorithms with Polynomially-Improved Approximation Factors for the 2 rightarrow q Norm, and Applications](https://mlsanity.com/paper/2605.25303/) (2026)

## Abstract (arXiv)

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.