{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:04:30Z","timestamp":1725563070255},"publisher-location":"Berlin, Heidelberg","reference-count":28,"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_23","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T00:01:36Z","timestamp":1282867296000},"page":"298-311","source":"Crossref","is-referenced-by-count":3,"title":["Approximate Lasserre Integrality Gap for Unique Games"],"prefix":"10.1007","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Preyas","family":"Popat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rishi","family":"Saket","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.4086\/toc.2006.v002a002","volume":"2","author":"S. Arora","year":"2006","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L., Tourlakis, I.: Proving integrality gaps without knowing the linear program. Theory of Computing\u00a02(1), 19\u201351 (2006)","journal-title":"Theory of Computing"},{"issue":"1","key":"23_CR2","first-page":"1","volume":"21","author":"S. Arora","year":"2008","unstructured":"Arora, S., Lee, J.R., Naor, A.: Euclidean distortion and the sparsest cut. J. AMS\u00a021(1), 1\u201321 (2008)","journal-title":"J. AMS"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proc. 36th ACM STOC, pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for unique games. In: Proc. 38th ACM STOC, pp. 205\u2013214 (2006)","DOI":"10.1145\/1132516.1132547"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: Proc. 41st ACM STOC, pp. 283\u2013292 (2009)","DOI":"10.1145\/1536414.1536455"},{"issue":"5","key":"23_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/j.crma.2006.07.001","volume":"343","author":"J. Cheeger","year":"2006","unstructured":"Cheeger, J., Kleiner, B.: Generalized differentiation and bi-Lipschitz nonembedding in L1. Comptes Rendus Mathematique\u00a0343(5), 297\u2013301 (2006)","journal-title":"Comptes Rendus Mathematique"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Cheeger, J., Kleiner, B., Naor, A.: A (logn)\u03a9(1) integrality gap for the sparsest cut SDP. In: Proc. 50th IEEE FOCS (2009)","DOI":"10.1109\/FOCS.2009.47"},{"key":"23_CR8","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of the johnson-lindenstrauss lemma. Tech. Rep. TR-99-006, U. C. Berkeley (1999)"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Devanur, N., Khot, S., Saket, R., Vishnoi, N.: Integrality gaps for sparsest cut and minimum linear arrangement problems. In: Proc. 38th ACM STOC, pp. 537\u2013546 (2006)","DOI":"10.1145\/1132516.1132594"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2 - o(1) for vertex cover SDPs in the Lov\u00e9sz-Schrijver hierarchy. In: Proc. 48th IEEE FOCS, pp. 702\u2013712 (2007)","DOI":"10.1109\/FOCS.2007.35"},{"issue":"6","key":"23_CR11","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"23_CR12","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proc. 44th IEEE FOCS (2003)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Talwar, K.: Approximating unique games. In: SODA 2006: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm (2006)","DOI":"10.1145\/1109557.1109569"},{"issue":"4","key":"23_CR14","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. J. ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"23_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W. Johnson","year":"1984","unstructured":"Johnson, W., Lindenstrauss, J.: Extensions of lipschitz maps into a hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. 34th ACM STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"issue":"1","key":"23_CR17","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 J. Comput.\u00a037(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S., Saket, R.: SDP integrality gaps with local \u21131-embeddability. In: Proc. 50th IEEE FOCS (2009)","DOI":"10.1109\/FOCS.2009.37"},{"key":"23_CR19","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 l1. In: Proc. 46th IEEE FOCS, pp. 53\u201362 (2005)","DOI":"10.1145\/2629614"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Rabani, Y.: Improved lower bounds for embeddings into l 1. In: ACM SODA, pp. 1010\u20131017 (2006)","DOI":"10.1145\/1109557.1109669"},{"key":"23_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45535-3_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.B. Lasserre","year":"2001","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 293\u2013303. Springer, Heidelberg (2001)"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Naor, A.: l p metrics on the Heisenberg group and the Goemans-Linial conjecture. In: Proc. 47th IEEE FOCS, pp. 99\u2013108 (2006)","DOI":"10.1109\/FOCS.2006.47"},{"key":"23_CR23","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low infuences invariance and optimality. In: Proc. 46th IEEE FOCS (2005)"},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Integrality gaps for strong SDP relaxations of Unique Games. In: Proc. 50th IEEE FOCS (2009)","DOI":"10.1109\/FOCS.2009.73"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: Proc. 49th IEEE FOCS, pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: A linear round lower bound for Lovasz-Schrijver SDP relaxations of vertex cover. In: IEEE Conference on Computational Complexity, pp. 205\u2013216 (2007)","DOI":"10.1109\/CCC.2007.2"},{"key":"23_CR27","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lovasz-Schrijver lp relaxations of vertex cover and max cut. In: Proc. 39th ACM STOC, pp. 302\u2013310 (2007)","DOI":"10.1145\/1250790.1250836"},{"key":"23_CR28","unstructured":"Trevisan, L.: Approximation algorithms for Unique Games. In: Proc. 46th IEEE FOCS (2005)"}],"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_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:05:23Z","timestamp":1606169123000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}