On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
share
A μ-constrained Boolean Max-CSP(ψ) instance is a Boolean Max-CSP instance on predicate ψ:{0,1}^r →{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 Gap_ℓ,μ(ψ)/log(1/μ)^2 (ignoring factors depending on r) for any ℓ≥ℓ(μ,r). Here, Gap_ℓ,μ(ψ) is the optimal integrality gap of ℓ-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.
READ FULL TEXT