Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson, Ola Svensson

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>>