Approximating Linear Threshold Predicates

Approximating Linear Threshold Predicates. Cheraghchi, M., Håstad, J., Isaksson, M., & Svensson, O. In Proceedings of APPROX, pages 110–123, 2010. Extended version in ACM Transactions on Computation Theory (ToCT).

Link

Paper doi abstract bibtex

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 + ⋯ +w_n x_n)$ for some positive integer weights $w_1, ṡ, 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+ ⋯ + 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.

@INPROCEEDINGS{ref:conf:CHIS10,
  author =	 {Cheraghchi, Mahdi and H\r{a}stad, Johan and
                  Isaksson, Marcus and Svensson, Ola},
  title =	 {Approximating Linear Threshold Predicates},
  booktitle =	 "Proceedings of {APPROX}",
  year =	 2010,
  pages =	 "110--123",
  url_Link =
                  {https://link.springer.com/chapter/10.1007/978-3-642-15369-3_9},
  doi =		 {10.1007/978-3-642-15369-3_9},
  keywords =	 {linear threshold predicates, constraint satisfactory
                  problems, approximation algorithms},
  note =	 {Extended version in {ACM Transactions on Computation
                  Theory (ToCT).}},
  url_Paper =	 {https://eccc.weizmann.ac.il//report/2010/132},
  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 $\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 \textit{Chow-robustness} that might be of
                  independent interest.}
}

Downloads: 0