{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T10:05:46Z","timestamp":1775729146700,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,5,8]],"date-time":"2014-05-08T00:00:00Z","timestamp":1399507200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10107-014-0785-x","type":"journal-article","created":{"date-parts":[[2014,5,7]],"date-time":"2014-05-07T13:02:02Z","timestamp":1399467722000},"page":"179-199","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the existence of 0\/1 polytopes with high semidefinite extension complexity"],"prefix":"10.1007","volume":"153","author":[{"given":"Jop","family":"Bri\u00ebt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Dadush","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,5,8]]},"reference":[{"key":"785_CR1","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1287\/moor.26.2.193.10561","volume":"26","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26, 193\u2013205 (2001). doi: 10.1287\/moor.26.2.193.10561","journal-title":"Math. Oper. Res."},{"key":"785_CR2","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S.: Common information and unique disjointness. In: IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS 2013), pp.\u00a0688\u2013697. Berkeley, California (2013)","DOI":"10.1109\/FOCS.2013.79"},{"key":"785_CR3","doi-asserted-by":"crossref","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (Beyond Hierarchies). In: 53rd IEEE Symposium on Foundations of Computer Science (FOCS 2012), pp. 480\u2013489 (2012). ISBN 978-1-4673-4383-1. doi: 10.1109\/FOCS.2012.10","DOI":"10.1109\/FOCS.2012.10"},{"key":"785_CR4","doi-asserted-by":"crossref","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, pp.\u00a0161\u2013170. ACM (2013)","DOI":"10.1145\/2488608.2488629"},{"key":"785_CR5","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. In: Mahjoub, A., Markakis, V., Milis, I., Paschos, V. (eds.) Combinatorial Optimization, volume 7422 of Lecture Notes in Computer Science, pp. 129\u2013140. Springer, Berlin (2012). ISBN 978-3-642-32146-7. doi: 10.1007\/978-3-642-32147-4_13 .","DOI":"10.1007\/978-3-642-32147-4_13"},{"key":"785_CR6","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs semidefinite extended formulations exponential: separation and strong lower bounds. In: Proceedings of STOC (2012a)","DOI":"10.1145\/2213977.2213988"},{"key":"785_CR7","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Rothvo\u00df, T., Tiwary, H.R.: Extended formulations for polygons. Discret. Comput. Geom. 48(3), 658\u2013668 (2012b). ISSN 0179\u20135376. doi: 10.1007\/s00454-012-9421-9","DOI":"10.1007\/s00454-012-9421-9"},{"key":"785_CR8","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Smallest compact formulation for the permutahedron. Math. Program. 1\u20137 (2014). doi: 10.1007\/s10107-014-0757-1","DOI":"10.1007\/s10107-014-0757-1"},{"issue":"2","key":"785_CR9","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1287\/moor.1120.0575","volume":"38","author":"J Gouveia","year":"2011","unstructured":"Gouveia, J., Parrilo, P.A., Thomas, R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248\u2013264 (2011)","journal-title":"Math. Oper. Res."},{"key":"785_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1210-2","volume-title":"Diophantine Geometry: An Introduction","author":"M Hindry","year":"2000","unstructured":"Hindry, M., Silverman, J.H.: Diophantine Geometry: An Introduction. Springer, Berlin (2000)"},{"key":"785_CR11","unstructured":"John, F.: Extremum problems with inequalities as subsidiary conditions. In: Studies and Essays Presented to R. Courant on his 60th Birthday, pp. 187\u2013204 (1948)"},{"key":"785_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-66282-9","volume-title":"Perturbation Theory for Linear Operators","author":"T Kat\u014d","year":"1995","unstructured":"Kat\u014d, T.: Perturbation Theory for Linear Operators. Springer, Berlin (1995)"},{"key":"785_CR13","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: Some 0\/1 polytopes need exponential size extended formulations. Math. Program. 142(1\u20132), 255\u2013268 (2013).\u00a0doi: 10.1007\/s10107-012-0574-3","DOI":"10.1007\/s10107-012-0574-3"},{"key":"785_CR14","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The Matching Polytope has Exponential Extension Complexity. ArXiv e-prints (2013)","DOI":"10.1145\/2591796.2591834"},{"key":"785_CR15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"25","author":"CE Shannon","year":"1949","unstructured":"Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 25, 59\u201398 (1949)","journal-title":"Bell Syst. Tech. J."},{"key":"785_CR16","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of the STOC 1988, pp. 223\u2013228 (1988)","DOI":"10.1145\/62212.62232"},{"issue":"3","key":"785_CR17","doi-asserted-by":"crossref","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: 10.1016\/0022-0000(91)90024-Y","journal-title":"J. Comput. Syst. Sci."},{"key":"785_CR18","doi-asserted-by":"crossref","unstructured":"Ziegler, G.M.: Lectures on 0\/1-Polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes-Combinatorics and Computation, Volume 29 of DMV Seminar, pp. 1\u201341. Birkh\u00e4user Basel (2000). ISBN 978-3-7643-6351-2. doi: 10.1007\/978-3-0348-8438-9_1","DOI":"10.1007\/978-3-0348-8438-9_1"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0785-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0785-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0785-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T08:02:59Z","timestamp":1565424179000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0785-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,8]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["785"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0785-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,8]]}}}