{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T10:05:43Z","timestamp":1775729143224,"version":"3.50.1"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T00:00:00Z","timestamp":1430870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARC"},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"publisher","award":["255961, 600700"],"award-info":[{"award-number":["255961, 600700"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,5,6]]},"abstract":"<jats:p>We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.<\/jats:p>","DOI":"10.1145\/2716307","type":"journal-article","created":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T16:30:57Z","timestamp":1431361857000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":86,"title":["Exponential Lower Bounds for Polytopes in Combinatorial Optimization"],"prefix":"10.1145","volume":"62","author":[{"given":"Samuel","family":"Fiorini","sequence":"first","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Massar","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans Raj","family":"Tiwary","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[{"name":"CWI and University of Amsterdam"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5,6]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704447237"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.35"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of FOCS","author":"Arora S.","year":"2002","unstructured":"S. Arora , B. Bollob\u00e1s , and L. Lov\u00e1sz . 2002. Proving integrality gaps without knowing the linear program . In Proceedings of FOCS 2002 . 313--322. S. Arora, B. Bollob\u00e1s, and L. Lov\u00e1sz. 2002. Proving integrality gaps without knowing the linear program. In Proceedings of FOCS 2002. 313--322."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_6"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0606047"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581273"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_23"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.10"},{"key":"e_1_2_2_10_1","unstructured":"G. Braun S. Fiorini and S. Pokutta. 2013a. Average case polyhedral complexity of the maximum stable set problem. arXiv:1311.4001.  G. Braun S. Fiorini and S. Pokutta. 2013a. Average case polyhedral complexity of the maximum stable set problem. arXiv:1311.4001."},{"key":"e_1_2_2_11_1","unstructured":"G. Braun R. Jain T. Lee and S. Pokutta. 2013b. Information-theoretic approximations of the nonnegative rank. ECCC Report no. 158 (2013).  G. Braun R. Jain T. Lee and S. Pokutta. 2013b. Information-theoretic approximations of the nonnegative rank. ECCC Report no. 158 (2013)."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.79"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"J.\n      Bri\u00ebt D.\n      Dadush and \n      S.\n      Pokutta\n  . \n  2013\n  . On the existence of 0\/1 polytopes with high semidefinite extension complexity. In Algorithms ESA 2013 Lecture Notes in Computer Science vol. \n  8125 Springer 217--228.  J. Bri\u00ebt D. Dadush and S. Pokutta. 2013. On the existence of 0\/1 polytopes with high semidefinite extension complexity. In Algorithms ESA 2013 Lecture Notes in Computer Science vol. 8125 Springer 217--228.","DOI":"10.1007\/978-3-642-40450-4_19"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.82.665"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a004"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.45"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"M. Conforti G. Cornu\u00e9jols and G. Zambelli. 2010. Extended formulations in combinatorial optimization. 4OR 8 1--48.  M. Conforti G. Cornu\u00e9jols and G. Zambelli. 2010. Extended formulations in combinatorial optimization. 4OR 8 1--48.","DOI":"10.1007\/s10288-010-0122-z"},{"key":"e_1_2_2_20_1","volume-title":"Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13","author":"Dantzig G. B.","unstructured":"G. B. Dantzig . 1951. Maximization of a linear function of variables subject to linear inequalities . In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13 , John Wiley & Sons Inc ., New York, 339--347. G. B. Dantzig. 1951. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, John Wiley & Sons Inc., New York, 339--347."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90056-N"},{"key":"e_1_2_2_22_1","volume-title":"Geometry of Cuts and Metrics. Algorithms and Combinatorics Series","volume":"15","author":"Deza M. M.","unstructured":"M. M. Deza and M. Laurent . 1997 . Geometry of Cuts and Metrics. Algorithms and Combinatorics Series , vol. 15 , Springer-Verlag. M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Algorithms and Combinatorics Series, vol. 15, Springer-Verlag."},{"key":"e_1_2_2_23_1","unstructured":"A. Drucker and R. de Wolf. 2011. Quantum proofs for classical theorems. Theory Comput. Graduate Surveys 2.  A. Drucker and R. de Wolf. 2011. Quantum proofs for classical theorems. Theory Comput. Graduate Surveys 2."},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Y. Faenza S. Fiorini R. Grappe and H. R. Tiwary. 2011. Extended formulations non-negative factorizations and randomized communication protocols. arXiv:1105.4127.  Y. Faenza S. Fiorini R. Grappe and H. R. Tiwary. 2011. Extended formulations non-negative factorizations and randomized communication protocols. arXiv:1105.4127.","DOI":"10.1007\/978-3-642-32147-4_13"},{"key":"e_1_2_2_25_1","unstructured":"H. Fawzi and P. A. Parrilo. 2013. Exponential lower bounds on fixed-size PSD rank and semidefinite extension complexity. arXiv:1311.2571.  H. Fawzi and P. A. Parrilo. 2013. Exponential lower bounds on fixed-size PSD rank and semidefinite extension complexity. arXiv:1311.2571."},{"key":"e_1_2_2_26_1","volume-title":"Proceedings of SODA","author":"Fernandez de la Vega W.","year":"2007","unstructured":"W. Fernandez de la Vega and C. Mathieu . 2007. Linear programming relaxation of Maxcut . In Proceedings of SODA 2007 . 53--61. W. Fernandez de la Vega and C. Mathieu. 2007. Linear programming relaxation of Maxcut. In Proceedings of SODA 2007. 53--61."},{"key":"e_1_2_2_27_1","unstructured":"S. Fiorini V. Kaibel K. Pashkovich and D. O. Theis. 2011. Combinatorial bounds on nonnegative rank and extended formulations. arXiv:1111.0444.  S. Fiorini V. Kaibel K. Pashkovich and D. O. Theis. 2011. Combinatorial bounds on nonnegative rank and extended formulations. arXiv:1111.0444."},{"key":"e_1_2_2_28_1","unstructured":"S. Fiorini S. Massar M. K. Patra and H. R. Tiwary. 2013. Generalised probabilistic theories and conic extensions of polytopes. CoRR abs\/1310.4125.  S. Fiorini S. Massar M. K. Patra and H. R. Tiwary. 2013. Generalised probabilistic theories and conic extensions of polytopes. CoRR abs\/1310.4125."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/080721479"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_10"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/090746525"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0575"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2746-4"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2258372"},{"key":"e_1_2_2_37_1","first-page":"2","article-title":"Extended formulations in combinatorial optimization","volume":"85","author":"Kaibel V.","year":"2011","unstructured":"V. Kaibel . 2011 . Extended formulations in combinatorial optimization . Optima 85 , 2 -- 7 . V. Kaibel. 2011. Extended formulations in combinatorial optimization. Optima 85, 2--7.","journal-title":"Optima"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_11"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-014-9655-9"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_2_42_1","unstructured":"L. G. Khachiyan. 1979. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR244 5 1093--1096.  L. G. Khachiyan. 1979. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR244 5 1093--1096."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_2_44_1","unstructured":"H. Klauck T. Lee and S. Zhang. 2011. An explicit and exponential separation between randomized and quantum correlation complexities. Unpublished manuscript from Oct\/Nov 2011. Personal communication between Troy Lee and Ronald de Wolf December 2011 at Centre for Quantum Technologies Singapore.  H. Klauck T. Lee and S. Zhang. 2011. An explicit and exponential separation between randomized and quantum correlation complexities. Unpublished manuscript from Oct\/Nov 2011. Personal communication between Troy Lee and Ronald de Wolf December 2011 at Centre for Quantum Technologies Singapore."},{"key":"e_1_2_2_45_1","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press.   E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748024"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536479"},{"key":"e_1_2_2_48_1","volume-title":"Proceedings of STOC","author":"Lee J. R.","year":"2015","unstructured":"J. R. Lee , P. Raghavendra , and D. Steurer . 2015. Lower bounds on the size of semidefinite programming relaxations . In Proceedings of STOC 2015 . J. R. Lee, P. Raghavendra, and D. Steurer. 2015. Lower bounds on the size of semidefinite programming relaxations. In Proceedings of STOC 2015."},{"key":"e_1_2_2_49_1","unstructured":"T. Lee and D. O. Theis. 2012. Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix. arXiv:1203.3961.  T. Lee and D. O. Theis. 2012. Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix. arXiv:1203.3961."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_2_2_51_1","first-page":"137","article-title":"Semidefinite programs and combinatorial optimization. In Recent Advances in Algorithms and Combinatorics. CMS Books Math.\/Ouvrages Math","volume":"11","author":"Lov\u00e1sz L.","year":"2003","unstructured":"L. Lov\u00e1sz . 2003 . Semidefinite programs and combinatorial optimization. In Recent Advances in Algorithms and Combinatorics. CMS Books Math.\/Ouvrages Math , SMC Series , vol. 11 , Spring er, 137 -- 194 . L. Lov\u00e1sz. 2003. Semidefinite programs and combinatorial optimization. In Recent Advances in Algorithms and Combinatorics. CMS Books Math.\/Ouvrages Math, SMC Series, vol. 11, Springer, 137--194.","journal-title":"SMC Series"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90035-U"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_2_2_54_1","volume-title":"Quantum Computer Science: An Introduction","author":"Mermin N. D.","unstructured":"N. D. Mermin . 2007. Quantum Computer Science: An Introduction . Cambridge University Press . N. D. Mermin. 2007. Quantum Computer Science: An Introduction. Cambridge University Press."},{"key":"e_1_2_2_55_1","unstructured":"M. A. Nielsen and I. L. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press.   M. A. Nielsen and I. L. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press."},{"key":"e_1_2_2_56_1","unstructured":"K. Pashkovich. 2009. Symmetry in extended formulations of the permutahedron. arXiv:0912.3446.  K. Pashkovich. 2009. Symmetry in extended formulations of the permutahedron. arXiv:0912.3446."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.03.010"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_2_2_59_1","doi-asserted-by":"crossref","unstructured":"T. Rothvoss. 2011. Some 0\/1 polytopes need exponential size extended formulations. arXiv:1105.0036.  T. Rothvoss. 2011. Some 0\/1 polytopes need exponential size extended formulations. arXiv:1105.0036.","DOI":"10.1007\/s10107-012-0574-3"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591834"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250836"},{"key":"e_1_2_2_62_1","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"A. Schrijver . 2003. Combinatorial Optimization. Polyhedra and Efficiency . Springer-Verlag . A. Schrijver. 2003. Combinatorial Optimization. Polyhedra and Efficiency. Springer-Verlag."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_2_65_1","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","unstructured":"M. Sipser . 1996. Introduction to the Theory of Computation . PWS , Boston, MA . M. Sipser. 1996. Introduction to the Theory of Computation. PWS, Boston, MA."},{"key":"e_1_2_2_66_1","volume-title":"rep","author":"Swart E. R.","unstructured":"E. R. Swart . 1986; revision 1987. P &equals; NP. Tech . rep ., University of Guelph. E. R. Swart. 1986; revision 1987. P &equals; NP. Tech. rep., University of Guelph."},{"key":"e_1_2_2_67_1","doi-asserted-by":"crossref","unstructured":"F. Vanderbeck and L. A. Wolsey. 2010. Reformulation and decomposition of integer programs. In 50 Years of Integer Programming 1958-2008 M. J\u00fcnger Th M. Liebling D. Naddef G. L. Nemhauser W. R. Pulleyblank G. Reinelt G. Rinaldi and L. A. Wolsey Eds. Springer 431--502.  F. Vanderbeck and L. A. Wolsey. 2010. Reformulation and decomposition of integer programs. In 50 Years of Integer Programming 1958-2008 M. J\u00fcnger Th M. Liebling D. Naddef G. L. Nemhauser W. R. Pulleyblank G. Reinelt G. Rinaldi and L. A. Wolsey Eds. Springer 431--502.","DOI":"10.1007\/978-3-540-68279-0_13"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00377-8"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702407345"},{"key":"e_1_2_2_70_1","first-page":"7","article-title":"Using extended formulations in practice","volume":"85","author":"Wolsey L. A.","year":"2011","unstructured":"L. A. Wolsey . 2011 . Using extended formulations in practice . Optima 85 , 7 -- 9 . L. A. Wolsey. 2011. Using extended formulations in practice. Optima 85, 7--9.","journal-title":"Optima"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62232"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"e_1_2_2_73_1","volume-title":"Lectures on Polytopes. Graduate Texts in Mathematics","author":"Ziegler G. M.","unstructured":"G. M. Ziegler . 1995. Lectures on Polytopes. Graduate Texts in Mathematics , vol. 152 . Springer-Verlag . G. M. Ziegler. 1995. Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer-Verlag."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2716307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2716307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:42Z","timestamp":1750230042000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2716307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,6]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5,6]]}},"alternative-id":["10.1145\/2716307"],"URL":"https:\/\/doi.org\/10.1145\/2716307","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,6]]},"assertion":[{"value":"2012-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}