Change search
ReferencesLink to record
Permanent link

Direct link
Approximating linear threshold predicates
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2012 (English)In: ACM Transactions on Computation Theory, ISSN 1942-3454, Vol. 4, no 1, 2- p.Article in journal (Refereed) Published
Abstract [en]

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(w 1x 1 + · · · + w nx n) for some positive integer weights w 1, . . . , 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 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(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.

Place, publisher, year, edition, pages
2012. Vol. 4, no 1, 2- p.
Keyword [en]
Approximation algorithms, Constraint satisfactory problems, Linear threshold predicates
National Category
Computer Science
URN: urn:nbn:se:kth:diva-99508DOI: 10.1145/2141938.2141940ScopusID: 2-s2.0-84859376220OAI: diva2:542415
QC 20120801Available from: 2012-08-01 Created: 2012-07-31 Last updated: 2012-08-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link