On the Approximability of Presidential Type Predicates

Neng Huang, Aaron Potechin

Given a predicate $P:\{-1,1{\}}^k\to \{-1,1\}$, let $CSP(P)$ be the set of constraint satisfaction problems whose constraints are of the form $P$. We say that $P$ is approximable…