{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:53Z","timestamp":1781077733600,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T00:00:00Z","timestamp":1307318400000},"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":[[2011,6,6]]},"DOI":"10.1145\/1993636.1993725","type":"proceedings-article","created":{"date-parts":[[2011,6,6]],"date-time":"2011-06-06T11:53:52Z","timestamp":1307361232000},"page":"665-674","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP"],"prefix":"10.1145","author":[{"given":"Yuichi","family":"Yoshida","sequence":"first","affiliation":[{"name":"Kyoto University & Preferred Infrastructure, Kyoto, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,6,6]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"crossref","unstructured":"Noga Alon. On constant time approximation of parameters of bounded degree graphs 2010. manuscript.  Noga Alon. On constant time approximation of parameters of bounded degree graphs 2010. manuscript.","DOI":"10.1007\/978-3-642-16367-8_14"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00008-4"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10041"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250818"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.20"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652193"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.684077"},{"key":"e_1_3_2_2_9_1","unstructured":"Dimitris A. Fotakis and Paul G. Spirakis. Linear programming and fast parallel approximability 1997. manuscript.  Dimitris A. Fotakis and Paul G. Spirakis. Linear programming and fast parallel approximability 1997. manuscript."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050060"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.51"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.49"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Subhash Khot and Assaf Naor. Sharp kernel clustering algorithms and their associated grothendieck inequalities. CoRR abs\/0906.4816 2009.  Subhash Khot and Assaf Naor. Sharp kernel clustering algorithms and their associated grothendieck inequalities. CoRR abs\/0906.4816 2009.","DOI":"10.1137\/1.9781611973075.55"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109666"},{"key":"e_1_3_2_2_21_1","unstructured":"Amit Kumar Rajsekar Manokaran Madhur Tulsiani and Nisheeth K. Vishnoi. On the optimality of a class of LP-based algorithms. CoRR abs\/0912.1776 2009.  Amit Kumar Rajsekar Manokaran Madhur Tulsiani and Nisheeth K. Vishnoi. On the optimality of a class of LP-based algorithms. CoRR abs\/0912.1776 2009."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374379"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.74"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132519"},{"key":"e_1_3_2_2_28_1","first-page":"239","volume-title":"Surveys in Combinatorics","author":"Wormald Nick","year":"1999"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.10"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536447"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276869"}],"event":{"name":"STOC'11: Symposium on Theory of Computing","location":"San Jose California USA","acronym":"STOC'11","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-third annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993725","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1993636.1993725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:11Z","timestamp":1750244771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1993636.1993725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,6]]},"references-count":31,"alternative-id":["10.1145\/1993636.1993725","10.1145\/1993636"],"URL":"https:\/\/doi.org\/10.1145\/1993636.1993725","relation":{},"subject":[],"published":{"date-parts":[[2011,6,6]]},"assertion":[{"value":"2011-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}