Approximating Linear Threshold Predicates. Cheraghchi, M., Hå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 1 download 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, ṡ, 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: 1
{"_id":"gqKWr2G9b7pGWE74N","bibbaseid":"cheraghchi-hastad-isaksson-svensson-approximatinglinearthresholdpredicates-2010","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M.","Håstad, J.","Isaksson, M.","Svensson, O."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Cheraghchi"],"firstnames":["Mahdi"],"suffixes":[]},{"propositions":[],"lastnames":["Håstad"],"firstnames":["Johan"],"suffixes":[]},{"propositions":[],"lastnames":["Isaksson"],"firstnames":["Marcus"],"suffixes":[]},{"propositions":[],"lastnames":["Svensson"],"firstnames":["Ola"],"suffixes":[]}],"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 + ⋯ +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 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 <i>Chow-robustness</i> that might be of independent interest.","bibtex":"@INPROCEEDINGS{ref:conf:CHIS10,\n author =\t {Cheraghchi, Mahdi and H\\r{a}stad, Johan and\n Isaksson, Marcus and Svensson, Ola},\n title =\t {Approximating Linear Threshold Predicates},\n booktitle =\t \"Proceedings of {APPROX}\",\n year =\t 2010,\n pages =\t \"110--123\",\n url_Link =\n {https://link.springer.com/chapter/10.1007/978-3-642-15369-3_9},\n doi =\t\t {10.1007/978-3-642-15369-3_9},\n keywords =\t {linear threshold predicates, constraint satisfactory\n problems, approximation algorithms},\n note =\t {Extended version in {ACM Transactions on Computation\n Theory (ToCT).}},\n url_Paper =\t {https://eccc.weizmann.ac.il//report/2010/132},\n abstract =\t {We study constraint satisfaction problems on the\n domain $\\{-1,1\\}$, where the given constraints are\n homogeneous linear threshold predicates. That is,\n predicates of the form $\\mathrm{sgn}(w_1 x_1 +\n \\cdots +w_n x_n)$ for some positive integer weights\n $w_1, \\dots, w_n$. Despite their simplicity, current\n techniques fall short of providing a classification\n of these predicates in terms of approximability. In\n fact, it is not easy to guess whether there exists a\n homogeneous linear threshold predicate that is\n approximation resistant or not. The focus of this\n paper is to identify and study the approximation\n curve of a class of threshold predicates that allow\n for non-trivial approximation. Arguably the\n simplest such predicate is the majority predicate\n $\\mathrm{sgn}(x_1+ \\cdots + x_n)$, for which we\n obtain an almost complete understanding of the\n asymptotic approximation curve, assuming the Unique\n Games Conjecture. Our techniques extend to a more\n general class of \"majority-like\" predicates and we\n obtain parallel results for them. In order to\n classify these predicates, we introduce the notion\n of \\textit{Chow-robustness} that might be of\n independent interest.}\n}\n\n","author_short":["Cheraghchi, M.","Håstad, J.","Isaksson, M.","Svensson, O."],"key":"ref:conf:CHIS10","id":"ref:conf:CHIS10","bibbaseid":"cheraghchi-hastad-isaksson-svensson-approximatinglinearthresholdpredicates-2010","role":"author","urls":{" link":"https://link.springer.com/chapter/10.1007/978-3-642-15369-3_9"," paper":"https://eccc.weizmann.ac.il//report/2010/132"},"keyword":["linear threshold predicates","constraint satisfactory problems","approximation algorithms"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/writings/"}},"downloads":1,"html":""},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T17:05:16.368Z","downloads":1,"keywords":["linear threshold predicates","constraint satisfactory problems","approximation algorithms"],"search_terms":["approximating","linear","threshold","predicates","cheraghchi","håstad","isaksson","svensson"],"title":"Approximating Linear Threshold Predicates","year":2010,"dataSources":["YZqdBBx6FeYmvQE6D"]}