{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:34:46Z","timestamp":1725744886380},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_19","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T03:22:47Z","timestamp":1376623367000},"page":"217-228","source":"Crossref","is-referenced-by-count":10,"title":["On the Existence of 0\/1 Polytopes with High Semidefinite Extension Complexity"],"prefix":"10.1007","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","reference":[{"key":"19_CR1","first-page":"1105","volume":"arXiv","author":"T. Rothvo\u00df","year":"2012","unstructured":"Rothvo\u00df, T.: Some 0\/1 polytopes need exponential size extended formulations. Math. Programming, arXiv:1105.0036 (2012)","journal-title":"Math. Programming"},{"key":"19_CR2","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 2012 (2012)","DOI":"10.1145\/2213977.2213988"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation Limits of Linear Programs (Beyond Hierarchies). In: 53rd IEEE Symp. on Foundations of Computer Science (FOCS 2012), pp. 480\u2013489 (2012)","DOI":"10.1109\/FOCS.2012.10"},{"issue":"3","key":"19_CR4","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. System Sci.\u00a043(3), 441\u2013466 (1991)","journal-title":"J. Comput. System Sci."},{"key":"19_CR5","doi-asserted-by":"publisher","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.\u00a026, 193\u2013205 (2001)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"19_CR6","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1007\/s00454-012-9421-9","volume":"48","author":"S. Fiorini","year":"2012","unstructured":"Fiorini, S., Rothvo\u00df, T., Tiwary, H.R.: Extended formulations for polygons. Discrete & Computational Geometry\u00a048(3), 658\u2013668 (2012)","journal-title":"Discrete & Computational Geometry"},{"key":"19_CR7","unstructured":"Goemans, M.X.: Smallest compact formulation for the permutahedron. Manuscript (2009)"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proc. STOC 1988, pp. 223\u2013228 (1988)","DOI":"10.1145\/62212.62232"},{"issue":"2","key":"19_CR9","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.: Lifts of convex sets and cone factorizations. Math. Oper. Res.\u00a038(2), 248\u2013264 (2011)","journal-title":"Math. Oper. Res."},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"25","author":"C.E. Shannon","year":"1949","unstructured":"Shannon, C.E.: The synthesis of two-terminal switching circuits. Bell System Tech. J.\u00a025, 59\u201398 (1949)","journal-title":"Bell System Tech. J."},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. Electronic Colloquium on Computational Complexity (ECCC)\u00a019(131) (2012)","DOI":"10.1145\/2488608.2488629"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-642-32147-4_13","volume-title":"Combinatorial Optimization","author":"Y. Faenza","year":"2012","unstructured":"Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol.\u00a07422, pp. 129\u2013140. Springer, Heidelberg (2012)"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S.: Common information and unique disjointness (submitted, 2013)","DOI":"10.1109\/FOCS.2013.79"},{"key":"19_CR14","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":"19_CR15","doi-asserted-by":"crossref","unstructured":"G\u00fcnter, M.: Lectures on 0\/1-Polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes \u2014 Combinatorics and Computation. DMV Seminar, vol.\u00a029, pp. 1\u201341. Birkh\u00e4user Basel (2000)","DOI":"10.1007\/978-3-0348-8438-9_1"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,3]],"date-time":"2023-07-03T21:54:05Z","timestamp":1688421245000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}