All reports by Author Ola Svensson:

__
TR10-132
| 18th August 2010
__

Mahdi Cheraghchi, Johan Hastad, Marcus Isaksson, Ola Svensson#### Approximating Linear Threshold Predicates

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