{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:39Z","timestamp":1740109239696,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T00:00:00Z","timestamp":1482364800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,12,22]],"date-time":"2016-12-22T00:00:00Z","timestamp":1482364800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["1333789","1452463"],"award-info":[{"award-number":["1333789","1452463"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1407779"],"award-info":[{"award-number":["1407779"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1106400"],"award-info":[{"award-number":["DGE-1106400"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s10107-016-1098-z","type":"journal-article","created":{"date-parts":[[2016,12,24]],"date-time":"2016-12-24T06:30:56Z","timestamp":1482561056000},"page":"643-662","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The matching problem has no small symmetric SDP"],"prefix":"10.1007","volume":"165","author":[{"given":"G\u00e1bor","family":"Braun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonah","family":"Brown-Cohen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arefin","family":"Huq","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aurko","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Weitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Zink","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,22]]},"reference":[{"key":"1098_CR1","doi-asserted-by":"publisher","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor $$2 - \\varepsilon $$. In: Proceedings of the FOCS, pp. 1123\u20131142 (2015). doi:\n                    10.1109\/FOCS.2015.73","DOI":"10.1109\/FOCS.2015.73"},{"key":"1098_CR2","doi-asserted-by":"publisher","unstructured":"Braun, G., Pokutta, S.: An algebraic approach to symmetric extended formulations. In: Proceedings of the ISCO, pp. 141\u2013152. Springer, Heidelberg, ISBN 978-3-642-32147-4 (2012). doi:\n                    10.1007\/978-3-642-32147-4_14","DOI":"10.1007\/978-3-642-32147-4_14"},{"key":"1098_CR3","doi-asserted-by":"publisher","unstructured":"Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proceedings of the SODA, pp. 837\u2013846 (2015a). doi:\n                    10.1137\/1.9781611973730.57","DOI":"10.1137\/1.9781611973730.57"},{"issue":"10","key":"1098_CR4","doi-asserted-by":"publisher","first-page":"5754","DOI":"10.1109\/TIT.2015.2465864","volume":"61","author":"G Braun","year":"2015","unstructured":"Braun, G., Pokutta, S.: The matching problem has no fully polynomial size linear programming relaxation schemes. IEEE Trans. Inf. Theory 61(10), 5754\u20135764 (2015). doi:\n                    10.1109\/TIT.2015.2465864","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1098_CR5","doi-asserted-by":"crossref","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: Proceedings of the FOCS, pp. 480\u2013489 (2012)","DOI":"10.1109\/FOCS.2012.10"},{"issue":"3","key":"1098_CR6","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1287\/moor.2014.0694","volume":"40","author":"G Braun","year":"2015","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3), 756\u2013772 (2015a). doi:\n                    10.1287\/moor.2014.0694","journal-title":"Math. Oper. Res."},{"key":"1098_CR7","doi-asserted-by":"publisher","unstructured":"Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs. In: Proceedings of the STOC, pp. 107\u2013116 (2015b). doi:\n                    10.1145\/2746539.2746550","DOI":"10.1145\/2746539.2746550"},{"key":"1098_CR8","doi-asserted-by":"publisher","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the STOC, pp. 161\u2013170. ACM, ISBN 978-1-4503-2029-0 (2013). doi:\n                    10.1145\/2488608.2488629","DOI":"10.1145\/2488608.2488629"},{"key":"1098_CR9","doi-asserted-by":"crossref","unstructured":"Bri\u00ebt, J., Dadush, D., Pokutta, S.: On the existence of 0\/1 polytopes with high semidefinite extension complexity. In: Proceedings of the ESA, pp. 217\u2013228. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40450-4_19"},{"issue":"1","key":"1098_CR10","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s10107-014-0785-x","volume":"153","author":"J Bri\u00ebt","year":"2015","unstructured":"Bri\u00ebt, J., Dadush, D., Pokutta, S.: On the existence of 0\/1 polytopes with high semidefinite extension complexity. Math. Program. 153(1), 179\u2013199 (2015). doi:\n                    10.1007\/s10107-014-0785-x","journal-title":"Math. Program."},{"key":"1098_CR11","doi-asserted-by":"crossref","unstructured":"Buss, S., Grigoriev, D., Impagliazzo, R., Pitassi, T.: Linear gaps between degrees for the polynomial calculus modulo distinct primes. In: Proceedings of the STOC, pp. 547\u2013556 (1999)","DOI":"10.1145\/301250.301399"},{"key":"1098_CR12","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: Proceedings of the FOCS, pp. 350\u2013359 (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"1098_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0731-3","volume-title":"Permutation Groups","author":"JD Dixon","year":"1996","unstructured":"Dixon, J.D., Mortimer, B.: Permutation Groups. Springer, Berlin (1996)"},{"key":"1098_CR14","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with $$0,1$$-vertices. J. Res. Nat. Bur. Stand. Sect. B 69B, 125\u2013130 (1965)","journal-title":"J. Res. Nat. Bur. Stand. Sect. B"},{"key":"1098_CR15","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.\u00a0R., de\u00a0Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the STOC, pp. 95\u2013106 (2012)","DOI":"10.1145\/2213977.2213988"},{"issue":"2","key":"1098_CR16","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de\u00a0Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. Assoc. Comput. Mach. 62(2), 17 (2015). doi:\n                    10.1145\/2716307","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"1098_CR17","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-014-0757-1","volume":"153","author":"MX Goemans","year":"2015","unstructured":"Goemans, M.X.: Smallest compact formulation for the permutahedron. Math. Program. 153(1), 5\u201311 (2015). doi:\n                    10.1007\/s10107-014-0757-1","journal-title":"Math. Program."},{"key":"1098_CR18","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. J. Assoc. Comput. Mach. 42, 1115\u20131145 (1995). doi:\n                    10.1145\/227683.227684","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"1098_CR19","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1287\/moor.1120.0575","volume":"38","author":"J Gouveia","year":"2011","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248\u2013264 (2011)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1098_CR20","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), 613\u2013622 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"1098_CR21","doi-asserted-by":"publisher","unstructured":"Kaibel, V., Pashkovich, K., Theis, D.O.: Symmetry matters for the sizes of extended formulations. In: Proceedings of the IPCO, pp. 135\u2013148 (2010). doi:\n                    10.1007\/978-3-642-13036-6_11","DOI":"10.1007\/978-3-642-13036-6_11"},{"key":"1098_CR22","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D., Tan, N.: On the power of symmetric LP and SDP relaxations. In: Proceedings of the CCC, pp. 13\u201321 (2014)","DOI":"10.1109\/CCC.2014.10"},{"key":"1098_CR23","doi-asserted-by":"publisher","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of the STOC, pp. 567\u2013576 (2015). doi:\n                    10.1145\/2746539.2746599","DOI":"10.1145\/2746539.2746599"},{"issue":"4","key":"1098_CR24","doi-asserted-by":"publisher","first-page":"1330","DOI":"10.1287\/moor.2014.0659","volume":"39","author":"K Pashkovich","year":"2014","unstructured":"Pashkovich, K.: Tight lower bounds on the sizes of symmetric extensions of permutahedra and similar results. Math. Oper. Res. 39(4), 1330\u20131339 (2014). doi:\n                    10.1287\/moor.2014.0659","journal-title":"Math. Oper. Res."},{"key":"1098_CR25","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of the STOC, pp. 263\u2013272 (2014)","DOI":"10.1145\/2591796.2591834"},{"key":"1098_CR26","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD 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 J. Discrete Math. 3, 411\u2013430 (1990). doi:\n                    10.1137\/0403036","journal-title":"SIAM J. Discrete Math."},{"key":"1098_CR27","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49\u201395 (1996)","journal-title":"SIAM Rev."},{"key":"1098_CR28","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of the STOC, pp. 223\u2013228 (1988)","DOI":"10.1145\/62212.62232"},{"issue":"3","key":"1098_CR29","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991). doi:\n                    10.1016\/0022-0000(91)90024-Y","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1098-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1098-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1098-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:18:48Z","timestamp":1589645928000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1098-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,22]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["1098"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1098-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2016,12,22]]},"assertion":[{"value":"17 January 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}