Approximating linear threshold predicates

• 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 1 x 1 + · · · + w n x 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.

Subject headings

NATURVETENSKAP  -- Matematik -- Beräkningsmatematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Computational Mathematics (hsv//eng)

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

NATURVETENSKAP  -- Matematik -- Matematisk analys (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Mathematical Analysis (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Keyword

Approximation algorithms

Linear threshold predicates

Constraint satisfactory problems

Publication and Content Type

art (subject category)

ref (subject category)