{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:35Z","timestamp":1750308635678,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,3,1]],"date-time":"2012-03-01T00:00:00Z","timestamp":1330560000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["2.26E+11"],"award-info":[{"award-number":["2.26E+11"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"publisher","award":["PBELP2-133367"],"award-info":[{"award-number":["PBELP2-133367"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p>\n            We study constraint satisfaction problems on the domain {\u22121, 1}, where the given constraints are homogeneous linear threshold predicates, that is, predicates of the form sgn(\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            + \u22ef +\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>n<\/jats:sub>\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>n<\/jats:sub>\n            ) for some positive integer weights\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , ...,\n            <jats:italic>w<\/jats:italic>\n            <jats:sub>n<\/jats:sub>\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.\n          <\/jats:p>\n          <jats:p>\n            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(\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            + \u22ef +\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>n<\/jats:sub>\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 \u201cmajority-like\u201d predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of\n            <jats:italic>Chow-robustness<\/jats:italic>\n            that might be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/2141938.2141940","type":"journal-article","created":{"date-parts":[[2012,3,27]],"date-time":"2012-03-27T15:17:31Z","timestamp":1332861451000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating Linear Threshold Predicates"],"prefix":"10.1145","volume":"4","author":[{"given":"Mahdi","family":"Cheraghchi","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Isaksson","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology and University of Gothenburg"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique F\u00e9d\u00e9ral de Lausanne"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783534"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.20"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_30"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1961.24"},{"key":"e_1_2_1_5_1","volume-title":"Threshold Logic: A Synthesis Approach","author":"Dertouzos M.","year":"1965","unstructured":"Dertouzos , M. 1965 . Threshold Logic: A Synthesis Approach . MIT Press , Cambridge, MA . Dertouzos, M. 1965. Threshold Logic: A Synthesis Approach. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_12"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1965.264254"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(63)80014-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374450"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374425"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01121471"},{"volume-title":"Threshold logic in artificial intelligence","author":"Winder R. O.","key":"e_1_2_1_19_1","unstructured":"Winder , R. O. 1963. Threshold logic in artificial intelligence . IEEE Artif. Intell. S- 142, 107--128. Winder, R. O. 1963. Threshold logic in artificial intelligence. IEEE Artif. Intell. S-142, 107--128."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1969.222665"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. H. J. Karloff Ed., ACM\/SIAM, 201--210","author":"Zwick U.","year":"1998","unstructured":"Zwick , U. 1998 . Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. H. J. Karloff Ed., ACM\/SIAM, 201--210 . Zwick, U. 1998. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. H. J. Karloff Ed., ACM\/SIAM, 201--210."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2141938.2141940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2141938.2141940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:08:04Z","timestamp":1750273684000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2141938.2141940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1145\/2141938.2141940"],"URL":"https:\/\/doi.org\/10.1145\/2141938.2141940","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2012,3]]},"assertion":[{"value":"2010-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}