{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:41:33Z","timestamp":1750308093154,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2005,5,22]],"date-time":"2005-05-22T00:00:00Z","timestamp":1116720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2005,5,22]]},"DOI":"10.1145\/1060590.1060700","type":"proceedings-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:31:47Z","timestamp":1123057907000},"page":"740-746","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Every 2-CSP allows nontrivial approximation"],"prefix":"10.1145","author":[{"given":"Johan","family":"H\u00e5stad","sequence":"first","affiliation":[{"name":"Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,5,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0805002"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1154"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.39"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20026"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_10_1","volume-title":"Computers and Intractability","author":"Garey M.R.","year":"1979","unstructured":"M.R. Garey and D.S. Johnson . Computers and Intractability . W.H. Freeman and Company , 1979 . M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and Company, 1979."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796391"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1162"},{"key":"e_1_3_2_1_14_1","unstructured":"G. Hast. Beating a random assignment. Manuscript.  G. Hast. Beating a random assignment. Manuscript."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875607"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.49"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"e_1_3_2_1_23_1","first-page":"117","volume-title":"On systems of linear equations with two variables per equation","author":"Feige U.","year":"2004","unstructured":"U. Feige and D. Reichman . On systems of linear equations with two variables per equation . In K. Jansen, S. Khanna, J. Rolim, and D. Ron, editors, Approximation, Randomization and Combinatorial Optimization, pages 117 -- 127 , 2004 . Proceedings of Approx 2004 and Random 2004, LNCS 3122. U. Feige and D. Reichman. On systems of linear equations with two variables per equation. In K. Jansen, S. Khanna, J. Rolim, and D. Ron, editors, Approximation, Randomization and Combinatorial Optimization, pages 117--127, 2004. Proceedings of Approx 2004 and Random 2004, LNCS 3122."},{"key":"e_1_3_2_1_24_1","first-page":"201","volume-title":"Proceedings 9th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Zwick U.","year":"1998","unstructured":"U. Zwick . Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint . In Proceedings 9th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 201 -- 210 . ACM, 1998 . U. Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 201--210. ACM, 1998."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301431"}],"event":{"name":"STOC05: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Baltimore MD USA","acronym":"STOC05"},"container-title":["Proceedings of the thirty-seventh annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1060590.1060700","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1060590.1060700","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:07:55Z","timestamp":1750262875000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1060590.1060700"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,22]]},"references-count":25,"alternative-id":["10.1145\/1060590.1060700","10.1145\/1060590"],"URL":"https:\/\/doi.org\/10.1145\/1060590.1060700","relation":{},"subject":[],"published":{"date-parts":[[2005,5,22]]},"assertion":[{"value":"2005-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}