On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs

Suprovat Ghoshal, Euiwoong Lee

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 ex…