Approximating Linear Threshold Predicates

Approximating Linear Threshold Predicates. Cheraghchi, M., Håstad, J., Isaksson, M., & Svensson, O. ACM Transactions on Computation Theory (ToCT), March, 2012. Preliminary version in Proceedings of APPROX 2010.

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.

@ARTICLE{ref:CHIS12,
  author =	 {Cheraghchi, Mahdi and H\r{a}stad, Johan and
                  Isaksson, Marcus and Svensson, Ola},
  title =	 {Approximating Linear Threshold Predicates},
  year =	 2012,
  volume =	 4,
  number =	 1,
  url_Link =	 {https://dl.acm.org/doi/10.1145/2141938.2141940},
  doi =		 {10.1145/2141938.2141940},
  journal =	 {ACM Transactions on Computation Theory (ToCT)},
  month =	 mar,
  articleno =	 2,
  numpages =	 31,
  keywords =	 {linear threshold predicates, constraint satisfactory
                  problems, approximation algorithms},
  note =	 {Preliminary version in {Proceedings of APPROX
                  2010.}},
  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