{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:59:05Z","timestamp":1781078345506,"version":"3.54.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,11,6]],"date-time":"2012-11-06T00:00:00Z","timestamp":1352160000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00037-012-0049-1","type":"journal-article","created":{"date-parts":[[2012,11,5]],"date-time":"2012-11-05T09:15:30Z","timestamp":1352106930000},"page":"191-213","source":"Crossref","is-referenced-by-count":3,"title":["Rank complexity gap for Lov\u00e1sz-Schrijver and Sherali-Adams proof systems"],"prefix":"10.1007","volume":"22","author":[{"given":"Stefan","family":"Dantchev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barnaby","family":"Martin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,11,6]]},"reference":[{"key":"49_CR1","doi-asserted-by":"crossref","unstructured":"Paul Beame, Trinh Huynh & Toniann Pitassi (2010). Hardness amplification in proof complexity. In STOC, Leonard J. Schulman, editor, 87\u201396. ACM. ISBN 978-1-4503-0050-6.","DOI":"10.1145\/1806689.1806703"},{"issue":"3","key":"49_CR2","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1137\/060654645","volume":"37","author":"Beame Paul","year":"2007","unstructured":"Paul Beame, Toniann Pitassi, Nathan Segerlind (2007) Lower Bounds for Lov\u00e1sz\u2013Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. SIAM J. Comput. 37(3): 845\u2013869","journal-title":"SIAM J. Comput."},{"key":"49_CR3","doi-asserted-by":"crossref","unstructured":"Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen & Toniann Pitassi (2006). Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory of Computing 2(1), 65\u201390. http:\/\/www.theoryofcomputing.org\/articles\/v002a004 .","DOI":"10.4086\/toc.2006.v002a004"},{"key":"49_CR4","doi-asserted-by":"crossref","unstructured":"Moses Charikar, Konstantin Makarychev & Yury Makarychev (2009). Integrality gaps for Sherali-Adams relaxations. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, 283\u2013292.","DOI":"10.1145\/1536414.1536455"},{"key":"49_CR5","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"Cook W., Coullard R., Turan G. (1987) On the complexity of cutting plane proofs. Discrete Applied Mathematics 18: 25\u201338","journal-title":"Discrete Applied Mathematics"},{"key":"49_CR6","doi-asserted-by":"crossref","unstructured":"S. Dantchev (2007). Rank complexity gap for Lov\u00e1sz-Schrijver and Sherali-Adams proof systems. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, 311\u2013317. ACM. ISBN 978-1-59593-631-8.","DOI":"10.1145\/1250790.1250837"},{"key":"49_CR7","unstructured":"S. Dantchev & S. Riis (2003). On Relativisation and Complexity gap for Resolution-based proof systems. In The 17th Annual Conference of the EACSL, Computer Science Logic, volume 2803 of LNCS, 142\u2013154. Springer."},{"key":"49_CR8","unstructured":"Stefan S. Dantchev & Barnaby Martin (2009). Cutting Planes and the Parameter Cutwidth. In CiE, 134\u2013143."},{"issue":"21\u201323","key":"49_CR9","doi-asserted-by":"crossref","first-page":"2054","DOI":"10.1016\/j.tcs.2009.01.002","volume":"410","author":"Dantchev Stefan S.","year":"2009","unstructured":"Stefan S. Dantchev, Barnaby Martin, Mark Rhodes (2009) Tight rank lower bounds for the Sherali-Adams proof system. Theor. Comput. Sci. 410(21\u201323): 2054\u20132063","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"49_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s00037-010-0001-1","volume":"20","author":"Dantchev Stefan S.","year":"2011","unstructured":"Stefan S. Dantchev, Barnaby Martin, Stefan Szeider (2011) Parameterized proof complexity. Comput. Complex. 20(1): 51\u201385","journal-title":"Comput. Complex."},{"key":"49_CR11","doi-asserted-by":"crossref","unstructured":"Konstantinos Georgiou, Avner Magen, Madhur Tulsiani (2009). Optimal Sherali-Adams Gaps from Pairwise Independence. In APPROX \u201909 \/ RANDOM \u201909: Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 125\u2013139. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-642-03684-2.","DOI":"10.1007\/978-3-642-03685-9_10"},{"key":"49_CR12","doi-asserted-by":"crossref","unstructured":"R. Gomory (1958) Outline of an algorithm for integer solutions to linear programs. Bulletin of the AMS (64), 275\u2013278.","DOI":"10.1090\/S0002-9904-1958-10224-4"},{"issue":"4","key":"49_CR13","doi-asserted-by":"crossref","first-page":"647","DOI":"10.17323\/1609-4514-2002-2-4-647-679","volume":"2","author":"D. Grigoriev","year":"2002","unstructured":"Grigoriev D., Hirsch E. A., Pasechnik D. V. (2002) Complexity of semialgebraic proofs. Moscow Mathematical Journal 2(4): 647\u2013679","journal-title":"Moscow Mathematical Journal"},{"issue":"3","key":"49_CR14","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. (2003) A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver and Lasserre relaxations for 0\u22121 programming. Mathematics of Operations Research 28(3): 470\u2013496","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"49_CR15","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"7","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz L., Schrijver A. (1991) Cones of matrices and set-functions and 0\u22121 optimization. SIAM Journal on Optimization 7(1): 166\u2013190","journal-title":"SIAM Journal on Optimization"},{"key":"49_CR16","doi-asserted-by":"crossref","unstructured":"Claire Mathieu & Alistair Sinclair (2009). Sherali-adams relaxations of the matching polytope. In STOC \u201909: Proceedings of the 41st annual ACM symposium on Theory of computing, 293\u2013302. ACM, New York, NY, USA. ISBN 978-1-60558-506-2.","DOI":"10.1145\/1536414.1536456"},{"key":"49_CR17","unstructured":"Toniann Pitassi & Nathan Segerlind (2009). Exponential lower bounds and integrality gaps for tree-like Lov\u00e1sz-Schrijver procedures. In SODA, 355\u2013364."},{"key":"49_CR18","doi-asserted-by":"crossref","unstructured":"P. Pudl\u00e1k (1999). On the complexity of propositional calculus. In Sets and Proofs, 197\u2013218. Cambridge University Press. Invited papers from Logic Colloquium\u201997.","DOI":"10.1017\/CBO9781107325944.010"},{"key":"49_CR19","doi-asserted-by":"crossref","unstructured":"Mark Rhodes (2008). Resolution Width and Cutting Plane Rank Are Incomparable. In MFCS, 575\u2013587.","DOI":"10.1007\/978-3-540-85238-4_47"},{"key":"49_CR20","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s00037-001-8194-y","volume":"10","author":"S. Riis","year":"2001","unstructured":"Riis S. (2001) A Complexity gap for tree-resolution. Computational Complexity 10: 179\u2013209","journal-title":"Computational Complexity"},{"key":"49_CR21","unstructured":"S\u00f8ren Riis (2008). On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity. In LICS, 272\u2013283."},{"key":"49_CR22","doi-asserted-by":"crossref","unstructured":"Grant Schoenebeck (2008). 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, 593\u2013602. IEEE Computer Society, Washington, DC, USA. ISBN 978-0-7695-3436-7.","DOI":"10.1109\/FOCS.2008.74"},{"key":"49_CR23","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H. D. Sherali","year":"1990","unstructured":"Sherali H. D., Adams W. P. (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3: 411\u2013430","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0049-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0049-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0049-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,5]],"date-time":"2019-07-05T07:23:03Z","timestamp":1562311383000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0049-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,6]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["49"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0049-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,6]]}}}