{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T03:14:07Z","timestamp":1764645247846,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"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_71","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"872-885","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On the Hardest Problem Formulations for the $$0\/1$$ Lasserre Hierarchy"],"prefix":"10.1007","author":[{"given":"Adam","family":"Kurpisz","sequence":"first","affiliation":[]},{"given":"Samuli","family":"Lepp\u00e4nen","sequence":"additional","affiliation":[]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"71_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: FOCS, pp. 563\u2013572 (2010)","DOI":"10.1109\/FOCS.2010.59"},{"key":"71_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. Journal of the ACM 56(2) (2009)","DOI":"10.1145\/1502793.1502794"},{"key":"71_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Brand\u00e3o, F.G.S.L., Harrow, A.W., Kelner, J.A., Steurer, D., Zhou, Y.: Hypercontractivity, sum-of-squares proofs, and their applications. In: STOC, pp. 307\u2013326 (2012)","DOI":"10.1145\/2213977.2214006"},{"key":"71_CR4","doi-asserted-by":"crossref","unstructured":"Barak, B., Chan, S.O., Kothari, P.: Sum of squares lower bounds from pairwise independence. In: STOC (2015)","DOI":"10.1145\/2746539.2746625"},{"key":"71_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B., Raghavendra, P., Steurer, D.: Rounding semidefinite programming hierarchies via global correlation. In: FOCS, pp. 472\u2013481 (2011)","DOI":"10.1109\/FOCS.2011.95"},{"key":"71_CR6","doi-asserted-by":"crossref","unstructured":"Bateni, M., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: STOC, pp. 543\u2013552 (2009)","DOI":"10.1145\/1536414.1536488"},{"key":"71_CR7","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Vijayaraghavan, A., Guruswami, V., Zhou, Y.: Polynomial integrality gaps for strong sdp relaxations of densest k-subgraph. In: SODA, pp. 388\u2013405 (2012)","DOI":"10.1137\/1.9781611973099.34"},{"issue":"1","key":"71_CR8","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1287\/moor.1060.0212","volume":"32","author":"KKH Cheung","year":"2007","unstructured":"Cheung, K.K.H.: Computation of the Lasserre ranks of some polytopes. Mathematics of Operations Research 32(1), 88\u201394 (2007)","journal-title":"Mathematics of Operations Research"},{"key":"71_CR9","doi-asserted-by":"crossref","unstructured":"Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: FOCS, pp. 691\u2013701 (2007)","DOI":"10.1109\/FOCS.2007.72"},{"key":"71_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-540-85363-3_5","volume-title":"Approximation, Randomization and Combinatorial Optimization","author":"E Chlamtac","year":"2008","unstructured":"Chlamtac, E., Singh, G.: Improved approximation guarantees through higher levels of SDP hierarchies. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 49\u201362. Springer, Heidelberg (2008)"},{"key":"71_CR11","series-title":"International Series in Operations Research & Management Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-1-4614-0769-0_6","volume-title":"Handbook on semidefinite, conic and polynomial optimization","author":"E Chlamtac","year":"2012","unstructured":"Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on semidefinite, conic and polynomial optimization. International Series in Operations Research & Management Science, vol. 166, pp. 139\u2013169. Springer, Heidelberg (2012)"},{"key":"71_CR12","doi-asserted-by":"crossref","unstructured":"Cygan, M., Grandoni, F., Mastrolilli, M.: How to sell hyperedges: the hypermatching assignment problem. In: SODA, pp. 342\u2013351 (2013)","DOI":"10.1137\/1.9781611973105.25"},{"key":"71_CR13","unstructured":"de la Vega, W.F., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: SODA, pp. 53\u201361 (2007)"},{"key":"71_CR14","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.: Sparse sum-of-squares certificates on finite abelian groups (2015). CoRR, abs\/1503.01207","DOI":"10.1109\/CDC.2015.7403148"},{"issue":"6","key":"71_CR15","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"},{"issue":"4","key":"71_CR16","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1137\/090746525","volume":"20","author":"J Gouveia","year":"2010","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Theta bodies for polynomial ideals. SIAM Journal on Optimization 20(4), 2097\u20132118 (2010)","journal-title":"SIAM Journal on Optimization"},{"issue":"2","key":"71_CR17","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00037-001-8192-0","volume":"10","author":"D Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Complexity of positivstellensatz proofs for the knapsack. Computational Complexity 10(2), 139\u2013154 (2001)","journal-title":"Computational Complexity"},{"issue":"1\u20132","key":"71_CR18","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1016\/S0304-3975(00)00157-2","volume":"259","author":"D Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science 259(1\u20132), 613\u2013622 (2001)","journal-title":"Theoretical Computer Science"},{"key":"71_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/3-540-45841-7_34","volume-title":"STACS 2002","author":"D Grigoriev","year":"2002","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semi-algebraic proofs. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol. 2285, p. 419. Springer, Heidelberg (2002)"},{"issue":"1\u20133","key":"71_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0168-0072(01)00055-0","volume":"113","author":"D Grigoriev","year":"2001","unstructured":"Grigoriev, D., Vorobjov, N.: Complexity of null-and positivstellensatz proofs. Annals of Pure and Applied Logic 113(1\u20133), 153\u2013160 (2001)","journal-title":"Annals of Pure and Applied Logic"},{"key":"71_CR21","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Sinop, A.K.: Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with psd objectives. In: FOCS, pp. 482\u2013491 (2011)","DOI":"10.1109\/FOCS.2011.36"},{"key":"71_CR22","unstructured":"Horn, R.A., Johnson, C.R.: Matrix analysis. Cambridge University Press (2013)"},{"key":"71_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-20807-2_24","volume-title":"Integer Programming and Combinatoral Optimization","author":"AR Karlin","year":"2011","unstructured":"Karlin, A.R., Mathieu, C., Nguyen, C.T.: Integrality gaps of linear and semi-definite programming relaxations for knapsack. In: G\u00fcnl\u00fck, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 301\u2013314. Springer, Heidelberg (2011)"},{"issue":"3","key":"71_CR24","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization 11(3), 796\u2013817 (2001)","journal-title":"SIAM Journal on Optimization"},{"issue":"3","key":"71_CR25","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver, and Lasserre relaxations for 0\u20131 programming. Mathematics of Operations Research 28(3), 470\u2013496 (2003)","journal-title":"Mathematics of Operations Research"},{"key":"71_CR26","first-page":"157","volume":"149","author":"M Laurent","year":"2009","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. Emerging Applications of Algebraic Geometry 149, 157\u2013270 (2009)","journal-title":"Emerging Applications of Algebraic Geometry"},{"key":"71_CR27","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: STOC (to appear, 2015)","DOI":"10.1145\/2746539.2746599"},{"key":"71_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the shannon capacity of a graph. IEEE Transactions on Information Theory 25, 1\u20137 (1979)","journal-title":"IEEE Transactions on Information Theory"},{"key":"71_CR29","doi-asserted-by":"crossref","unstructured":"Magen, A., Moharrami, M.: Robust algorithms for on minor-free graphs based on the Sherali-Adams hierarchy. In: APPROX-RANDOM, pp. 258\u2013271 (2009)","DOI":"10.1007\/978-3-642-03685-9_20"},{"key":"71_CR30","unstructured":"Nesterov, Y.: Global quadratic optimization via conic relaxation, pp. 363\u2013384. Kluwer Academic Publishers (2000)"},{"key":"71_CR31","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press (2014)"},{"key":"71_CR32","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Zhou, Y.: Approximability and proof complexity. In: SODA, pp. 1537\u20131556 (2013)","DOI":"10.1137\/1.9781611973105.111"},{"key":"71_CR33","unstructured":"Parrilo, P.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology (2000)"},{"key":"71_CR34","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Tan, N.: Approximating csps with global cardinality constraints using sdp hierarchies. In: SODA, pp. 373\u2013387 (2012)","DOI":"10.1137\/1.9781611973099.33"},{"key":"71_CR35","unstructured":"Rothvo\u00df, T.: The lasserre hierarchy in approximation algorithms. Lecture Notes for the MAPSP 2013 - Tutorial, June 2013"},{"key":"71_CR36","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-csps. In: FOCS, pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"issue":"6","key":"71_CR37","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/BF01070233","volume":"23","author":"N Shor","year":"1987","unstructured":"Shor, N.: Class of global minimum bounds of polynomial functions. Cybernetics 23(6), 731\u2013734 (1987)","journal-title":"Cybernetics"},{"key":"71_CR38","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: Csp gaps and reductions in the Lasserre hierarchy. In: 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":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:44:00Z","timestamp":1676018640000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}