{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:58:58Z","timestamp":1760061538683},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_30","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T18:35:59Z","timestamp":1464114959000},"page":"362-374","source":"Crossref","is-referenced-by-count":7,"title":["Sum-of-Squares Hierarchy Lower Bounds for Symmetric Formulations"],"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":[[2016,5,25]]},"reference":[{"key":"30_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":"30_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":"30_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":"30_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":"30_CR5","unstructured":"Barak, B., Steurer, D.: Sum-of-squares proofs, the quest toward optimal algorithms. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 21, p. 59 (2014)"},{"key":"30_CR6","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"},{"key":"30_CR7","unstructured":"Blekherman, G., Gouveia, J., Pfeiffer, J.: Sums of squares on the hypercube. In: CoRR, abs\/1402.4199 (2014)"},{"key":"30_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/978-3-540-68891-4_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"T Carnes","year":"2008","unstructured":"Carnes, T., Shmoys, D.B.: Primal-Dual schema for capacitated covering problems. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 288\u2013302. Springer, Heidelberg (2008)"},{"key":"30_CR9","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":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/978-3-642-13036-6_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"D Chakrabarty","year":"2010","unstructured":"Chakrabarty, D., Grant, E., K\u00f6nemann, J.: On column-restricted and priority covering integer programs. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 355\u2013368. Springer, Heidelberg (2010)"},{"key":"30_CR11","series-title":"International Series in Operations Research & Management Science","first-page":"139","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.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, US (2011)"},{"key":"30_CR12","unstructured":"Godsil, C.: Association schemes (2010). Lecture Notes available at http:\/\/quoll.uwaterloo.ca\/mine\/Notes\/assoc2.pdf"},{"issue":"4","key":"30_CR13","doi-asserted-by":"crossref","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)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"30_CR14","doi-asserted-by":"crossref","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":"30_CR15","doi-asserted-by":"crossref","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":"30_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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","key":"30_CR17","doi-asserted-by":"crossref","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)","journal-title":"Discrete Appl. Math."},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"30_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1007\/978-3-662-48350-3_71","volume-title":"Algorithms - ESA 2015","author":"A Kurpisz","year":"2015","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: A Lasserre lower bound for the min-sum single machine scheduling problem. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 853\u2013864. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48350-3_71"},{"key":"30_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1007\/978-3-662-47672-7_71","volume-title":"Automata, Languages, and Programming","author":"A Kurpisz","year":"2015","unstructured":"Kurpisz, A., Lepp\u00e4nen, S., Mastrolilli, M.: On the hardest problem formulations for the 0\/1 Lasserre hierarchy. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 872\u2013885. Springer, Heidelberg (2015)"},{"issue":"3","key":"30_CR21","doi-asserted-by":"crossref","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":"30_CR22","doi-asserted-by":"crossref","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":"30_CR23","doi-asserted-by":"crossref","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)","journal-title":"Math. Oper. Res."},{"key":"30_CR24","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: STOC, pp. 567\u2013576 (2015)","DOI":"10.1145\/2746539.2746599"},{"key":"30_CR25","doi-asserted-by":"crossref","unstructured":"Meka, R., Potechin, A., Wigderson, A.: Sum-of-squares lower bounds for planted clique. In: STOC, pp. 87\u201396 (2015)","DOI":"10.1145\/2746539.2746600"},{"key":"30_CR26","unstructured":"O\u2019Donnell, R.: Approximability proof complex. Talk at ELC Tokyo (2013). Slides available at http:\/\/www.cs.cmu.edu\/~odonnell\/slides\/approx-proof-cxty.pps"},{"key":"30_CR27","unstructured":"Parrilo, P.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.D. thesis. California Institute of Technology (2000)"},{"key":"30_CR28","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: STOC, pp. 245\u2013254 (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"30_CR29","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":"30_CR30","doi-asserted-by":"crossref","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":"30_CR31","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":"30_CR32","doi-asserted-by":"crossref","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":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-33461-5_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T15:47:11Z","timestamp":1567957631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}