{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:25Z","timestamp":1725558985104},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_52","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:02Z","timestamp":1278321962000},"page":"617-628","source":"Crossref","is-referenced-by-count":1,"title":["SDP Gaps for 2-to-1 and Other Label-Cover Variants"],"prefix":"10.1007","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[]},{"given":"Subhash","family":"Khot","sequence":"additional","affiliation":[]},{"given":"Ryan","family":"O\u2019Donnell","sequence":"additional","affiliation":[]},{"given":"Preyas","family":"Popat","sequence":"additional","affiliation":[]},{"given":"Madhur","family":"Tulsiani","sequence":"additional","affiliation":[]},{"given":"Yi","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"52_CR1","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1137\/050628957","volume":"36","author":"A. Bulatov","year":"2006","unstructured":"Bulatov, A., Dalmau, V.: A simple algorithm for Mal\u2019tsev constraints. SICOMP\u00a036(1), 16\u201327 (2006)","journal-title":"SICOMP"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for unique games. In: Proc. 38\n                    th\n                   ACM STOC, pp. 205\u2013214 (2006)","DOI":"10.1145\/1132516.1132547"},{"issue":"3","key":"52_CR3","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1137\/07068062X","volume":"39","author":"I. Dinur","year":"2009","unstructured":"Dinur, I., Mossel, E., Regev, O.: Conditional hardness for approximate coloring. SICOMP\u00a039(3), 843\u2013873 (2009)","journal-title":"SICOMP"},{"issue":"1","key":"52_CR4","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math.\u00a0162(1), 439\u2013486 (2005)","journal-title":"Ann. Math."},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Manokaran, R., Raghavendra, P.: Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In: Proc. 49\n                    th\n                   IEEE FOCS, pp. 573\u2013582 (2008)","DOI":"10.1109\/FOCS.2008.51"},{"key":"52_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-3-642-03685-9_13","volume-title":"APPROX 2009 and RANDOM 2009","author":"V. Guruswami","year":"2009","unstructured":"Guruswami, V., Sinop, A.K.: Improved inapproximability results for maximum k-colorable subgraph. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009 and RANDOM 2009. LNCS, vol.\u00a05687, pp. 163\u2013176. Springer, Heidelberg (2009)"},{"key":"52_CR7","unstructured":"Khot, S.: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In: Proc. 43\n                    rd\n                   IEEE FOCS, pp. 23\u201332 (2002)"},{"key":"52_CR8","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. 34\n                    th\n                   ACM STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"52_CR9","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: SDP integrality gaps with local \u21131-embeddability. In: Proc. 50\n                    th\n                   IEEE FOCS, pp. 565\u2013574 (2009)","DOI":"10.1109\/FOCS.2009.37"},{"key":"52_CR10","doi-asserted-by":"crossref","unstructured":"Khot, S., Vishnoi, N.: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative type metrics into \u21131. In: Proc. 46\n                    th\n                   IEEE FOCS, pp. 53\u201362 (2005)","DOI":"10.1145\/2629614"},{"key":"52_CR11","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wu, Y.: Conditional hardness for satisfiable CSPs. In: Proc. 41\n                    st\n                   ACM STOC, pp. 493\u2013502 (2009)","DOI":"10.1145\/1536414.1536482"},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proc. 40\n                    th\n                   ACM STOC, pp. 245\u2013254 (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"52_CR13","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Integrality gaps for strong SDP relaxations of unique games. In: Proc. 50\n                    th\n                   IEEE FOCS, pp. 575\u2013585 (2009)","DOI":"10.1109\/FOCS.2009.73"},{"key":"52_CR14","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: Proc. 49\n                    th\n                   IEEE FOCS, pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"issue":"3","key":"52_CR15","doi-asserted-by":"publisher","first-page":"1576","DOI":"10.1214\/aop\/1176988612","volume":"22","author":"M. Talagrand","year":"1994","unstructured":"Talagrand, M.: On Russo\u2019s approximate zero-one law. Ann. Prob.\u00a022(3), 1576\u20131587 (1994)","journal-title":"Ann. Prob."},{"key":"52_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1007\/978-3-642-10631-6_93","volume-title":"Algorithms and Computation","author":"L. Tang","year":"2009","unstructured":"Tang, L.: Conditional hardness of approximating satisfiable Max 3CSP-q. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 923\u2013932. Springer, Heidelberg (2009)"},{"key":"52_CR17","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: Proc. 41\n                    st\n                   ACM STOC, pp. 303\u2013312 (2009)","DOI":"10.1145\/1536414.1536457"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T15:40:09Z","timestamp":1558280409000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}