ECCC-Report TR10-132https://eccc.weizmann.ac.il/report/2010/132Comments and Revisions published for TR10-132en-usWed, 18 Aug 2010 20:57:56 +0300
Paper TR10-132
| Approximating Linear Threshold Predicates |
Mahdi Cheraghchi,
Johan Hastad,
Marcus Isaksson,
Ola Svensson
https://eccc.weizmann.ac.il/report/2010/132We 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 of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not.
The focus of this paper is to identify and study the approximation curve of a class of threshold predicates that allow for non-trivial approximation. Arguably the simplest such predicate is the majority predicate $\mathrm{sgn}(x_1 + \cdots + x_n)$, for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.
Wed, 18 Aug 2010 20:57:56 +0300https://eccc.weizmann.ac.il/report/2010/132