{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:57Z","timestamp":1781078337427,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_67","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"822-833","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximating CSPs Using LP Relaxation"],"prefix":"10.1007","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rishi","family":"Saket","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"67_CR1","doi-asserted-by":"crossref","unstructured":"Chan, S.O.: Approximation resistance from pairwise independent subgroups. In: Proc. STOC, pp. 447\u2013456 (2013)","DOI":"10.1145\/2488608.2488665"},{"key":"67_CR2","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for unique games. In: Proc. STOC, pp. 205\u2013214 (2006)","DOI":"10.1145\/1132516.1132547"},{"key":"67_CR3","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Krokhin, A.A., Manokaran, R.: Towards a characterization of constant-factor approximable min CSPs. In: Proc. SODA, pp. 847\u2013857 (2015)","DOI":"10.1137\/1.9781611973730.58"},{"key":"67_CR4","doi-asserted-by":"crossref","unstructured":"Dinur, I., Kol, G.: Covering CSPs. In: Proc. CCC, pp. 207\u2013218 (2013)","DOI":"10.1109\/CCC.2013.29"},{"issue":"3","key":"67_CR5","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1002\/rsa.10036","volume":"20","author":"U Feige","year":"2002","unstructured":"Feige, U., Schechtman, G.: On the optimality of the random hyperplane rounding technique for MAX CUT. Random Struct. Algorithms 20(3), 403\u2013440 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"6","key":"67_CR6","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6), 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"67_CR7","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"issue":"1","key":"67_CR8","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal of Computing 37(1), 319\u2013357 (2007)","journal-title":"SIAM Journal of Computing"},{"key":"67_CR9","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: Approximating CSPs using LP relaxation (2015). http:\/\/researcher.ibm.com\/researcher\/files\/in-rissaket\/KS-icalp-full.pdf","DOI":"10.1007\/978-3-662-47672-7_67"},{"key":"67_CR10","doi-asserted-by":"crossref","unstructured":"Khot, S., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $$\\ell _1$$. In: Proc. FOCS, pp. 53\u201362 (2005)","DOI":"10.1145\/2629614"},{"key":"67_CR11","doi-asserted-by":"crossref","unstructured":"Kindler, G., Kolla, A., Trevisan, L.: Approximation of non-boolean 2CSP (2015). CoRR, abs\/1504.00681. http:\/\/arxiv.org\/pdf\/1504.00681.pdf","DOI":"10.1137\/1.9781611974331.ch117"},{"key":"67_CR12","doi-asserted-by":"crossref","unstructured":"Kumar, A., Manokaran, R., Tulsiani, M., Vishnoi, N.K.: On LP-based approximability for strict CSPs. In: Proc. SODA, pp. 1560\u20131573 (2011)","DOI":"10.1137\/1.9781611973082.121"},{"key":"67_CR13","doi-asserted-by":"crossref","unstructured":"Kun, G., O\u2019Donnell, R., Tamaki, S., Yoshida, Y., Zhou, Y.: Linear programming, width-1 CSPs, and robust satisfaction. In: Proc. ITCS, pp. 484\u2013495 (2012)","DOI":"10.1145\/2090236.2090274"},{"key":"67_CR14","doi-asserted-by":"publisher","first-page":"341","DOI":"10.4086\/toc.2014.v010a013","volume":"10","author":"K Makarychev","year":"2014","unstructured":"Makarychev, K., Makarychev, Y.: Approximation algorithm for non-boolean Max-k-CSP. Theory of Computing 10, 341\u2013358 (2014)","journal-title":"Theory of Computing"},{"key":"67_CR15","first-page":"1713","volume":"19","author":"E Mossel","year":"2010","unstructured":"Mossel, E.: Gaussian bounds for noise correlation of functions. GAFA 19, 1713\u20131756 (2010)","journal-title":"GAFA"},{"issue":"1","key":"67_CR16","doi-asserted-by":"publisher","first-page":"295","DOI":"10.4007\/annals.2010.171.295","volume":"171","author":"E Mossel","year":"2010","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences: invariance and optimality. Annals of Mathematics 171(1), 295\u2013341 (2010)","journal-title":"Annals of Mathematics"},{"key":"67_CR17","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proc. STOC, pp. 245\u2013254 (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"67_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/BFb0028584","volume-title":"STACS 1998","author":"MJ Serna","year":"1998","unstructured":"Serna, M.J., Trevisan, L., Xhafa, F.: The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 488\u2013498. Springer, Heidelberg (1998)"},{"issue":"1","key":"67_CR19","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/PL00009209","volume":"21","author":"L Trevisan","year":"1998","unstructured":"Trevisan, L.: Parallel approximation algorithms by positive linear programming. Algorithmica 21(1), 72\u201388 (1998)","journal-title":"Algorithmica"},{"key":"67_CR20","doi-asserted-by":"publisher","first-page":"703","DOI":"10.4086\/toc.2013.v009a023","volume":"9","author":"C Wenner","year":"2013","unstructured":"Wenner, C.: Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four. Theory of Computing 9, 703\u2013757 (2013)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_67","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:15:33Z","timestamp":1676945733000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}