### Skapa referens, olika format (klipp och klistra)

**Harvard**

Cheraghchi, M., Håstad, J., Isaksson, M. och Svensson, O. (2010) *Approximating Linear Threshold Predicates*.

** BibTeX **

@conference{

Cheraghchi2010,

author={Cheraghchi, M. and Håstad, J. and Isaksson, Marcus and Svensson, O.},

title={Approximating Linear Threshold Predicates},

booktitle={Lecture Notes in Computer Science. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, 1-3 September 2010},

isbn={978-364215368-6},

pages={110-123},

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(w1 x1+⋯+wn 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 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 sgn(x 1+⋯+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.},

year={2010},

keywords={Approximability, constraint satisfaction problems, linear threshold predicates},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 155045

A1 Cheraghchi, M.

A1 Håstad, J.

A1 Isaksson, Marcus

A1 Svensson, O.

T1 Approximating Linear Threshold Predicates

YR 2010

T2 Lecture Notes in Computer Science. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, 1-3 September 2010

SN 978-364215368-6

SP 110

OP 123

AB 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(w1 x1+⋯+wn 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 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 sgn(x 1+⋯+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.

LA eng

DO 10.1007/978-3-642-15369-3_9

LK http://dx.doi.org/10.1007/978-3-642-15369-3_9

OL 30