{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,31]],"date-time":"2025-10-31T07:18:16Z","timestamp":1761895096936},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130359"},{"type":"electronic","value":"9783642130366"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13036-6_23","type":"book-chapter","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:36:09Z","timestamp":1276000569000},"page":"299-312","source":"Crossref","is-referenced-by-count":6,"title":["Extending SDP Integrality Gaps to Sherali-Adams with Applications to Quadratic\u00a0Programming and MaxCutGain"],"prefix":"10.1007","author":[{"given":"Siavosh","family":"Benabbas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"23_CR1","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00222-005-0465-9","volume":"163","author":"N. Alon","year":"2006","unstructured":"Alon, N., Makarychev, K., Makarychev, Y., Naor, A.: Quadratic forms on graphs. Invent. Math.\u00a0163(3), 499\u2013522 (2006)","journal-title":"Invent. Math."},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1109\/SFCS.2005.57","volume-title":"FOCS \u201905: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science","author":"S. Arora","year":"2005","unstructured":"Arora, S., Berger, E., Kindler, G., Safra, M., Hazan, E.: On non-approximability for quadratic programs. In: FOCS \u201905: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 206\u2013215. IEEE Computer Society, Washington (2005)"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1536414.1536455","volume-title":"STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing","author":"M. Charikar","year":"2009","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for sherali-adams relaxations. In: STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing, pp. 283\u2013292. ACM, New York (2009)"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/FOCS.2004.39","volume-title":"FOCS \u201904: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science","author":"M. Charikar","year":"2004","unstructured":"Charikar, M., Wirth, A.: Maximizing quadratic programs: Extending grothendieck\u2019s inequality. In: FOCS \u201904: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 54\u201360. IEEE Computer Society, Washington (2004)"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Tulsiani, M.: Optimal sherali-adams gaps from pairwise independence. In: APPROX-RANDOM, pp. 125\u2013139 (2009)","DOI":"10.1007\/978-3-642-03685-9_10"},{"key":"23_CR6","first-page":"1","volume":"8","author":"A. Grothendieck","year":"1953","unstructured":"Grothendieck, A.: R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Bol. Soc. Mat. S\u00e3o Paulo\u00a08, 1\u201379 (1953)","journal-title":"Bol. Soc. Mat. S\u00e3o Paulo"},{"key":"23_CR7","first-page":"217","volume-title":"FOCS \u201906: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"S. Khot","year":"2006","unstructured":"Khot, S., O\u2019Donnell, R.: Sdp gaps and ugc-hardness for maxcutgain. In: FOCS \u201906: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 217\u2013226. IEEE Computer Society, Washington (2006)"},{"key":"23_CR8","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)"},{"issue":"2","key":"23_CR9","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0\u20131 optimization. SIAM Journal on Optimization\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/1536414.1536456","volume-title":"STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing","author":"C. Mathieu","year":"2009","unstructured":"Mathieu, C., Sinclair, A.: Sherali-adams relaxations of the matching polytope. In: STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing, pp. 293\u2013302. ACM, New York (2009)"},{"key":"23_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Springer, New York (2002)"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: How to round any csp. In: FOCS \u201909: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (to appear 2009)","DOI":"10.1109\/FOCS.2009.74"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Integrality gaps for strong sdp relaxations of unique games. In: FOCS \u201909: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (to appear 2009)","DOI":"10.1109\/FOCS.2009.73"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1109\/FOCS.2008.74","volume-title":"FOCS \u201908: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science","author":"G. Schoenebeck","year":"2008","unstructured":"Schoenebeck, G.: Linear level lasserre lower bounds for certain k-csps. In: FOCS \u201908: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 593\u2013602. IEEE Computer Society, Washington (2008)"},{"issue":"3","key":"23_CR15","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics\u00a03(3), 411\u2013430 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1145\/1536414.1536457","volume-title":"STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing","author":"M. Tulsiani","year":"2009","unstructured":"Tulsiani, M.: Csp gaps and reductions in the lasserre hierarchy. In: STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing, pp. 303\u2013312. ACM, New York (2009)"},{"key":"23_CR17","first-page":"53","volume-title":"SODA \u201907: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms","author":"W.F. Vega de la","year":"2007","unstructured":"de la Vega, W.F., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: SODA \u201907: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 53\u201361. Society for Industrial and Applied Mathematics, Philadelphia (2007)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13036-6_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:51:59Z","timestamp":1619783519000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13036-6_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130359","9783642130366"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13036-6_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}