{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:22:19Z","timestamp":1726410139762},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_9","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"110-123","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Linear Threshold Predicates"],"prefix":"10.1007","author":[{"given":"Mahdi","family":"Cheraghchi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus","family":"Isaksson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Austrin, P., H\u00e5stad, J.: Randomly supported independence and resistance. In: 38th Annual ACM Symposium on Theory of Computation, pp. 483\u2013492 (2009)","DOI":"10.1145\/1536414.1536481"},{"issue":"2","key":"9_CR2","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00037-009-0272-6","volume":"18","author":"P. Austrin","year":"2009","unstructured":"Austrin, P., Mossel, E.: Approximation resistant predicates from pairwise independence. Computational Complexity\u00a018(2), 249\u2013271 (2009)","journal-title":"Computational Complexity"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Chow, C.K.: On the characterization of threshold functions. In: Proceedings of the 2nd Annual Symposium on Switching Circuit Theory and Logical Design, pp. 34\u201338 (1961)","DOI":"10.1109\/FOCS.1961.24"},{"key":"9_CR4","volume-title":"Threshold logic: a synthesis approach","author":"M. Dertouzos","year":"1965","unstructured":"Dertouzos, M.: Threshold logic: a synthesis approach. MIT Press, Cambridge (1965)"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Servedio, R.A.: Improved approximation of linear threshold functions. In: IEEE Conference on Computational Complexity, pp. 161\u2013172 (2009)","DOI":"10.1109\/CCC.2009.8"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Hast, G.: Beating a random assignment. In: APPROX-RANDOM, pp. 134\u2013145 (2005)","DOI":"10.1007\/11538462_12"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of ACM\u00a048, 798\u2013859 (2001)","journal-title":"Journal of ACM"},{"issue":"2","key":"9_CR9","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1109\/PGEC.1965.264254","volume":"EC -14","author":"K.R. Kaplan","year":"1965","unstructured":"Kaplan, K.R., Winder, R.O.: Chebyshev approximation and threshold functions. IEEE Transactions on Electronic Computers\u00a0EC -14(2), 250\u2013252 (1965)","journal-title":"IEEE Transactions on Electronic Computers"},{"issue":"4","key":"9_CR10","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/S0019-9958(63)80014-5","volume":"6","author":"P. Kaszerman","year":"1963","unstructured":"Kaszerman, P.: A geometric test-synthesis procedure for a threshold device. Information and Control\u00a06(4), 381\u2013398 (1963)","journal-title":"Information and Control"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of 34th ACM Symposium on Theory of Computating, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S., Mossel, E., Kindler, G., O\u2019Donnell, R.: Optimal inapproximability results for Max-Cut and other 2-variable CSPs? In: Proceedings of 45th Annual IEEE Symposium of Foundations of Computer Science, pp. 146\u2013154 (2004)","DOI":"10.1109\/FOCS.2004.49"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Servedio, R.A.: The Chow parameters problem. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 517\u2013526 (2008)","DOI":"10.1145\/1374376.1374450"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wu, Y.: An optimal SDP algorithm for Max-Cut and equally optimal long code tests. In: Proceedings of 40th ACM Symposium on Theory of Computating, pp. 335\u2013344 (2008)","DOI":"10.1145\/1374376.1374425"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF01121471","volume":"35","author":"I.S. Shiganov","year":"1986","unstructured":"Shiganov, I.S.: Refinement of the upper bound of a constant in the remainder term of the central limit theorem. Journal of Soviet mathematics\u00a035, 109\u2013115 (1986)","journal-title":"Journal of Soviet mathematics"},{"key":"9_CR17","first-page":"107","volume":"S-142","author":"R.O. Winder","year":"1963","unstructured":"Winder, R.O.: Threshold logic in artificial intelligence. Artificial Intelligence\u00a0S-142, 107\u2013128 (1963)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"9_CR18","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1109\/T-C.1969.222665","volume":"18","author":"R.O. Winder","year":"1969","unstructured":"Winder, R.O.: Threshold gate approximations based on Chow parameters. IEEE Transactions on Computers\u00a018(4), 372\u2013375 (1969)","journal-title":"IEEE Transactions on Computers"},{"key":"9_CR19","unstructured":"Zwick, U.: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 201\u2013210 (1998)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:38Z","timestamp":1606187138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}