Approximating Linear Threshold Predicates

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola SvenssonACM Trans. Comput. Theory 2012 · DOI · OpenReview

Abstract

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 sgn(w1x1 + ⋯ + wnxn) for some positive integer weights w1, ..., wn. 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 article is to identify and study the approximation curve of a class of threshold predicates that allow for nontrivial approximation. Arguably the simplest such predicate is the majority predicate sgn(x1 + ⋯ + xn), 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.
BibTeX
@article{cheraghchi2012approximating,
  author = {Mahdi Cheraghchi and Johan Håstad and Marcus Isaksson and Ola Svensson},
  title = {{Approximating Linear Threshold Predicates}},
  journal = {ACM Trans. Comput. Theory},
  year = {2012},
  doi = {10.1145/2141938.2141940},
}

Loading related content...

Figure