{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T19:44:30Z","timestamp":1778615070025,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,5,19]],"date-time":"2012-05-19T00:00:00Z","timestamp":1337385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,5,19]]},"DOI":"10.1145\/2213977.2213988","type":"proceedings-article","created":{"date-parts":[[2012,5,21]],"date-time":"2012-05-21T15:20:35Z","timestamp":1337613635000},"page":"95-106","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":103,"title":["Linear vs. semidefinite extended formulations"],"prefix":"10.1145","author":[{"given":"Samuel","family":"Fiorini","sequence":"first","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}]},{"given":"Serge","family":"Massar","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander Universit\u00e4t, Erlangen, Germany"}]},{"given":"Hans Raj","family":"Tiwary","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[{"name":"CWI and University of Amsterdam, Amsterdam, Netherlands"}]}],"member":"320","published-online":{"date-parts":[[2012,5,19]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007358"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.35"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652188"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606047"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581273"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_23"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.82.665"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a004"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_3_2_2_11_1","volume-title":"Extended formulations in combinatorial optimization. 4OR, 8:1--48","author":"Conforti M.","year":"2010","unstructured":"M. Conforti , G. Cornu\u00e9jols , and G. Zambelli . Extended formulations in combinatorial optimization. 4OR, 8:1--48 , 2010 . M. Conforti, G. Cornu\u00e9jols, and G. Zambelli. Extended formulations in combinatorial optimization. 4OR, 8:1--48, 2010."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90056-N"},{"key":"e_1_3_2_2_13_1","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of cuts and metrics","author":"Deza M.M.","year":"1997","unstructured":"M.M. Deza and M. Laurent . Geometry of cuts and metrics , volume 15 of Algorithms and Combinatorics . Springer-Verlag , 1997 . M.M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, 1997."},{"key":"e_1_3_2_2_14_1","first-page":"2","article-title":"Quantum proofs for classical theorems. Theory Comput","author":"Drucker A.","year":"2011","unstructured":"A. Drucker and R. de Wolf . Quantum proofs for classical theorems. Theory Comput ., Graduate Surveys , 2 , 2011 . A. Drucker and R. de Wolf. Quantum proofs for classical theorems. Theory Comput., Graduate Surveys, 2, 2011.","journal-title":"Graduate Surveys"},{"key":"e_1_3_2_2_15_1","unstructured":"Y. Faenza S. Fiorini R. Grappe and H. R. Tiwary. Extended formulations non-negative factorizations and randomized communication protocols. http:\/\/arxiv.org\/abs\/1105.4127arXiv:1105.4127 2011.  Y. Faenza S. Fiorini R. Grappe and H. R. Tiwary. Extended formulations non-negative factorizations and randomized communication protocols. http:\/\/arxiv.org\/abs\/1105.4127arXiv:1105.4127 2011."},{"key":"e_1_3_2_2_16_1","first-page":"53","volume-title":"Proc. SODA 2007","author":"de la Vega W. Fernandez","year":"2007","unstructured":"W. Fernandez de la Vega and C. Mathieu . Linear programming relaxation of Maxcut . In Proc. SODA 2007 , pages 53 -- 61 , 2007 . W. Fernandez de la Vega and C. Mathieu. Linear programming relaxation of Maxcut. In Proc. SODA 2007, pages 53--61, 2007."},{"key":"e_1_3_2_2_17_1","unstructured":"S. Fiorini V. Kaibel K. Pashkovich and D. O. Theis. Combinatorial bounds on nonnegative rank and extended formulations. http:\/\/arxiv.org\/abs\/1111.0444arXiv:1111.0444 2011.  S. Fiorini V. Kaibel K. Pashkovich and D. O. Theis. Combinatorial bounds on nonnegative rank and extended formulations. http:\/\/arxiv.org\/abs\/1111.0444arXiv:1111.0444 2011."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/080721479"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_10"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/090746525"},{"key":"e_1_3_2_2_21_1","unstructured":"J. Gouveia P.A. Parrilo and R. Thomas. Lifts of convex sets and cone factorizations. http:\/\/arxiv.org\/abs\/1111.3164arXiv:1111.3164 2011.  J. Gouveia P.A. Parrilo and R. Thomas. Lifts of convex sets and cone factorizations. http:\/\/arxiv.org\/abs\/1111.3164arXiv:1111.3164 2011."},{"key":"e_1_3_2_2_22_1","unstructured":"H. Huang and B. Sudakov. A counterexample to the alon-saks-seymour conjecture and related problems. http:\/\/arxiv.org\/abs\/1002.4687arXiv:1002.4687 2010.  H. Huang and B. Sudakov. A counterexample to the alon-saks-seymour conjecture and related problems. http:\/\/arxiv.org\/abs\/1002.4687arXiv:1002.4687 2010."},{"key":"e_1_3_2_2_23_1","first-page":"2","article-title":"Extended formulations in combinatorial optimization","volume":"85","author":"Kaibel V.","year":"2011","unstructured":"V. Kaibel . Extended formulations in combinatorial optimization . Optima , 85 : 2 -- 7 , 2011 . V. Kaibel. Extended formulations in combinatorial optimization. Optima, 85:2--7, 2011.","journal-title":"Optima"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_11"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780560"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/264772"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748024"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536479"},{"key":"e_1_3_2_2_29_1","volume-title":"Convex analysis and minimization algorithms I","author":"Lemar\u00e9chal C.","year":"1996","unstructured":"C. Lemar\u00e9chal and J.B. Hiriart-Urruty . Convex analysis and minimization algorithms I . Springer , 1996 . C. Lemar\u00e9chal and J.B. Hiriart-Urruty. Convex analysis and minimization algorithms I. Springer, 1996."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-22444-0_6"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1296197"},{"key":"e_1_3_2_2_34_1","volume-title":"Quantum computation and quantum information","author":"Nielsen M. A.","year":"2000","unstructured":"M. A. Nielsen and I. L. Chuang . Quantum computation and quantum information . Cambridge University Press , 2000 . M. A. Nielsen and I. L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000."},{"key":"e_1_3_2_2_35_1","unstructured":"K. Pashkovich. Symmetry in extended formulations of the permutahedron. http:\/\/arxiv.org\/abs\/0912.3446arXiv:0912.3446 2009.  K. Pashkovich. Symmetry in extended formulations of the permutahedron. http:\/\/arxiv.org\/abs\/0912.3446arXiv:0912.3446 2009."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_2_37_1","volume-title":"http:\/\/arxiv.org\/abs\/1105.0036arXiv:1105.0036","author":"Rothvo\u00df T.","year":"2011","unstructured":"T. Rothvo\u00df . Some 0\/1 polytopes need exponential size extended formulations. http:\/\/arxiv.org\/abs\/1105.0036arXiv:1105.0036 , 2011 . T. Rothvo\u00df. Some 0\/1 polytopes need exponential size extended formulations. http:\/\/arxiv.org\/abs\/1105.0036arXiv:1105.0036, 2011."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250836"},{"key":"e_1_3_2_2_39_1","volume-title":"Polyhedra and efficiency","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver . Combinatorial optimization. Polyhedra and efficiency . Springer-Verlag , 2003 . A. Schrijver. Combinatorial optimization. Polyhedra and efficiency. Springer-Verlag, 2003."},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_2_42_1","volume-title":"Technical report","author":"Swart E. R.","year":"1986","unstructured":"E. R. Swart . P = NP. Technical report , University of Guelph , 1986 ; revision 1987. E. R. Swart. P = NP. Technical report, University of Guelph, 1986; revision 1987."},{"key":"e_1_3_2_2_43_1","first-page":"431","volume-title":"M. J\u00fcnger et al.","author":"Vanderbeck F.","year":"1958","unstructured":"F. Vanderbeck and L. A. Wolsey . Reformulation and decomposition of integer programs . In M. J\u00fcnger et al. , editor, 50 Years of Integer Programming 1958 --2008, pages 431 -- 502 . Springer , 2010. F. Vanderbeck and L. A. Wolsey. Reformulation and decomposition of integer programs. In M. J\u00fcnger et al., editor, 50 Years of Integer Programming 1958--2008, pages 431--502. Springer, 2010."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00377-8"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702407345"},{"key":"e_1_3_2_2_46_1","first-page":"7","article-title":"Using extended formulations in practice","volume":"85","author":"Wolsey L. A.","year":"2011","unstructured":"L. A. Wolsey . Using extended formulations in practice . Optima , 85 : 7 -- 9 , 2011 . L. A. Wolsey. Using extended formulations in practice. Optima, 85:7--9, 2011.","journal-title":"Optima"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62232"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"crossref","unstructured":"G. M.\n      Ziegler\n    . \n      Lectures\n       on \n      Polytopes volume \n  152\n   of \n  Graduate Texts in Mathematics\n  . \n  Springer-Verlag 1995\n  .  G. M. Ziegler. Lectures on Polytopes volume 152 of Graduate Texts in Mathematics. Springer-Verlag 1995.","DOI":"10.1007\/978-1-4613-8431-1"}],"event":{"name":"STOC'12: Symposium on Theory of Computing","location":"New York New York USA","acronym":"STOC'12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fourth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213988","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2213977.2213988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:20:54Z","timestamp":1750238454000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2213977.2213988"}},"subtitle":["exponential separation and strong lower bounds"],"short-title":[],"issued":{"date-parts":[[2012,5,19]]},"references-count":49,"alternative-id":["10.1145\/2213977.2213988","10.1145\/2213977"],"URL":"https:\/\/doi.org\/10.1145\/2213977.2213988","relation":{},"subject":[],"published":{"date-parts":[[2012,5,19]]},"assertion":[{"value":"2012-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}