{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:12Z","timestamp":1771623792344,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T00:00:00Z","timestamp":1558483200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T00:00:00Z","timestamp":1558483200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"crossref","award":["200020-144491\/1"],"award-info":[{"award-number":["200020-144491\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"crossref","award":["PZ00P2 174117"],"award-info":[{"award-number":["PZ00P2 174117"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s10107-019-01398-9","type":"journal-article","created":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T23:17:07Z","timestamp":1558567027000},"page":"369-397","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Sum-of-squares hierarchy lower bounds for symmetric formulations"],"prefix":"10.1007","volume":"182","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9500-1863","authenticated-orcid":false,"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":[[2019,5,22]]},"reference":[{"key":"1398_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: Randomized competitive algorithms for generalized caching. In: STOC, pp. 235\u2013244 (2008)","DOI":"10.1145\/1374376.1374412"},{"key":"1398_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., Krishnaswamy, R.: A constant factor approximation algorithm for generalized min-sum set cover. In: SODA, pp. 1539\u20131545 (2010)","DOI":"10.1137\/1.9781611973075.125"},{"key":"1398_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. In: FOCS, pp. 407\u2013414 (2010)","DOI":"10.1109\/FOCS.2010.46"},{"key":"1398_CR4","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":"1398_CR5","unstructured":"Barak, B., Chan, S.O., Kothari, P.: Sum of squares lower bounds from pairwise independence. In: STOC (2015). \narXiv:1501.00734"},{"key":"1398_CR6","first-page":"59","volume":"21","author":"B Barak","year":"2014","unstructured":"Barak, B., Steurer, D.: Sum-of-squares proofs and the quest toward optimal algorithms. Electron. Colloq. Comput. Complex. (ECCC) 21, 59 (2014)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"1398_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":"1398_CR8","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/S1052623402420346","volume":"15","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0\u20131 integer programming. SIAM J. Optim. 15(1), 63\u201395 (2004)","journal-title":"SIAM J. Optim."},{"key":"1398_CR9","unstructured":"Blekherman, G., ao\u00a0Gouveia, J., Pfeiffer, J.: Sums of squares on the hypercube. CoRR \narXiv:1402.4199\n\n (2014)"},{"key":"1398_CR10","doi-asserted-by":"publisher","unstructured":"Blekherman, G., Parrilo, P., Thomas, R.: Semidefinite optimization and convex algebraic geometry. Society for Industrial and Applied Mathematics, Philadelphia, PA (2012). \nhttps:\/\/doi.org\/10.1137\/1.9781611972290","DOI":"10.1137\/1.9781611972290"},{"key":"1398_CR11","doi-asserted-by":"crossref","unstructured":"Carnes, T., Shmoys, D.B.: Primal-dual schema for capacitated covering problems. In: IPCO, pp. 288\u2013302 (2008)","DOI":"10.1007\/978-3-540-68891-4_20"},{"key":"1398_CR12","unstructured":"Carr, R.D., Fleischer, L., Leung, V.J., Phillips, C.A.: Strengthening integrality gaps for capacitated network design and covering problems. In: SODA, pp. 106\u2013115 (2000)"},{"key":"1398_CR13","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Grant, E., K\u00f6nemann, J.: On column-restricted and priority covering integer programs. In: IPCO, pp. 355\u2013368 (2010)","DOI":"10.1007\/978-3-642-13036-6_27"},{"issue":"1","key":"1398_CR14","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. Math. Oper. Res. 32(1), 88\u201394 (2007)","journal-title":"Math. Oper. Res."},{"key":"1398_CR15","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":"2011","unstructured":"Chlamtac, E., Tulsiani, M.: Convex relaxations and integrality gaps. In: Anjos, M., Lasserre, J. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, vol. 166, pp. 139\u2013169. Springer, Berlin (2011)"},{"issue":"1","key":"1398_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1287\/moor.26.1.19.10593","volume":"26","author":"W Cook","year":"2001","unstructured":"Cook, W., Dash, S.: On the matrix-cut rank of polyhedra. Math. Oper. Res. 26(1), 19\u201330 (2001)","journal-title":"Math. Oper. Res."},{"key":"1398_CR17","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.: Sparse sum-of-squares certificates on finite Abelian groups. CoRR. \narXiv:1503.01207\n\n (2015)","DOI":"10.1109\/CDC.2015.7403148"},{"key":"1398_CR18","unstructured":"Godsil, C.: Association schemes (2010). Lecture Notes Available at \nhttp:\/\/quoll.uwaterloo.ca\/mine\/Notes\/assoc2.pdf"},{"issue":"4","key":"1398_CR19","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1287\/moor.26.4.796.10012","volume":"26","author":"MX Goemans","year":"2001","unstructured":"Goemans, M.X., Tun\u00e7el, L.: When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 26(4), 796\u2013815 (2001). \nhttps:\/\/doi.org\/10.1287\/moor.26.4.796.10012","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1398_CR20","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. Comput. Complex. 10(2), 139\u2013154 (2001)","journal-title":"Comput. Complex."},{"issue":"1\u20132","key":"1398_CR21","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. Theor. Comput. Sci. 259(1\u20132), 613\u2013622 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"1398_CR22","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semi-algebraic proofs. In: STACS, pp. 419\u2013430 (2002)","DOI":"10.1007\/3-540-45841-7_34"},{"issue":"1","key":"1398_CR23","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2007.07.021","volume":"156","author":"S Hong","year":"2008","unstructured":"Hong, S., Tun\u00e7el, L.: Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra. Discrete Appl. Math. 156(1), 25\u201341 (2008). \nhttps:\/\/doi.org\/10.1016\/j.dam.2007.07.021","journal-title":"Discrete Appl. Math."},{"key":"1398_CR24","doi-asserted-by":"publisher","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: STOC, pp. 767\u2013775 (2002). \nhttps:\/\/doi.org\/10.1145\/509907.510017","DOI":"10.1145\/509907.510017"},{"key":"1398_CR25","doi-asserted-by":"crossref","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: A Lasserre lower bound for the min-sum single machine scheduling problem. In: ESA, pp. 853\u2013864 (2015)","DOI":"10.1007\/978-3-662-48350-3_71"},{"key":"1398_CR26","doi-asserted-by":"crossref","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: On the hardest problem formulations for the 0\/1 lasserre hierarchy. In: ICALP, pp. 872\u2013885 (2015)","DOI":"10.1007\/978-3-662-47672-7_71"},{"key":"1398_CR27","doi-asserted-by":"publisher","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: Tight sum-of-squares lower bounds for binary polynomial optimization problems. pp. 78:1\u201378:14 (2016). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2016.78","DOI":"10.4230\/LIPIcs.ICALP.2016.78"},{"issue":"3","key":"1398_CR28","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 J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1398_CR29","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. Math. Oper. Res. 28(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1398_CR30","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4), 871\u2013883 (2003). \nhttps:\/\/doi.org\/10.1287\/moor.28.4.871.20508","journal-title":"Math. Oper. Res."},{"key":"1398_CR31","doi-asserted-by":"publisher","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: STOC, pp. 567\u2013576 (2015). \nhttps:\/\/doi.org\/10.1145\/2746539.2746599","DOI":"10.1145\/2746539.2746599"},{"key":"1398_CR32","doi-asserted-by":"publisher","unstructured":"Lee, T., Prakash, A., de\u00a0Wolf, R., Yuen, H.: On the sum-of-squares degree of symmetric quadratic functions. In: 31st Conference on Computational Complexity, CCC 2016, Tokyo, Japan, pp. 17:1\u201317:31 (2016). \nhttps:\/\/doi.org\/10.4230\/LIPIcs.CCC.2016.17","DOI":"10.4230\/LIPIcs.CCC.2016.17"},{"issue":"2","key":"1398_CR33","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 J. Optim. 1(2), 166\u2013190 (1991). \nhttps:\/\/doi.org\/10.1137\/0801013","journal-title":"SIAM J. Optim."},{"key":"1398_CR34","doi-asserted-by":"publisher","unstructured":"Meka, R., Potechin, A., Wigderson, A.: Sum-of-squares lower bounds for planted clique. In: STOC, pp. 87\u201396 (2015). \nhttps:\/\/doi.org\/10.1145\/2746539.2746600","DOI":"10.1145\/2746539.2746600"},{"key":"1398_CR35","unstructured":"O\u2019Donnell, R.: Approximability and proof complexity (2013). Talk at ELC Tokyo. Slides Available at \nhttp:\/\/www.cs.cmu.edu\/odonnell\/slides\/approx-proof-cxty.pps"},{"key":"1398_CR36","unstructured":"Parrilo, P.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology, California (2000)"},{"key":"1398_CR37","doi-asserted-by":"publisher","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: STOC, pp. 245\u2013254 (2008). \nhttps:\/\/doi.org\/10.1145\/1374376.1374414","DOI":"10.1145\/1374376.1374414"},{"key":"1398_CR38","unstructured":"Rothvo\u00df, T.: The lasserre hierarchy in approximation algorithms (2013). In: Lecture Notes for the MAPSP 2013\u2014Tutorial"},{"key":"1398_CR39","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":"1","key":"1398_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.24.1.1","volume":"24","author":"T Stephen","year":"1999","unstructured":"Stephen, T., Tun\u00e7el, L.: On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1), 1\u20137 (1999)","journal-title":"Math. Oper. Res."},{"key":"1398_CR41","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"},{"key":"1398_CR42","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/BF01580441","volume":"8","author":"LA Wolsey","year":"1975","unstructured":"Wolsey, L.A.: Facets for a linear inequality in 0\u20131 variables. Math. Program. 8, 168\u2013175 (1975)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01398-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01398-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01398-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T15:16:27Z","timestamp":1592925387000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01398-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,22]]},"references-count":42,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["1398"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01398-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,22]]},"assertion":[{"value":"9 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}