{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:55Z","timestamp":1740109255651,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T00:00:00Z","timestamp":1535155200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T00:00:00Z","timestamp":1535155200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000084","name":"Directorate for Engineering","doi-asserted-by":"publisher","award":["CMMI-1452463"],"award-info":[{"award-number":["CMMI-1452463"]}],"id":[{"id":"10.13039\/100000084","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10107-018-1316-y","type":"journal-article","created":{"date-parts":[[2018,8,25]],"date-time":"2018-08-25T03:33:03Z","timestamp":1535167983000},"page":"591-620","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Strong reductions for extended formulations"],"prefix":"10.1007","volume":"172","author":[{"given":"G\u00e1bor","family":"Braun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aurko","family":"Roy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,25]]},"reference":[{"issue":"1","key":"1316_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0894-0347-07-00573-5","volume":"21","author":"S Arora","year":"2008","unstructured":"Arora, S., Lee, J., Naor, A.: Euclidean distortion and the sparsest cut. J. Am. Math. Soc. 21(1), 1\u201321 (2008)","journal-title":"J. Am. Math. Soc."},{"key":"1316_CR2","doi-asserted-by":"publisher","unstructured":"Bansal, N., Khot, S.: Optimal long code test with one free bit. In: Proceedings of FOCS. IEEE (2009). \n                    https:\/\/doi.org\/10.1109\/FOCS.2009.23","DOI":"10.1109\/FOCS.2009.23"},{"key":"1316_CR3","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates Vertex Cover within a factor $$2-\\varepsilon $$. arXiv preprint \n                    arXiv:1503.00753\n                    \n                   (2015)","DOI":"10.1109\/FOCS.2015.73"},{"key":"1316_CR4","doi-asserted-by":"publisher","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). \n                    https:\/\/doi.org\/10.1109\/FOCS.2012.10","DOI":"10.1109\/FOCS.2012.10"},{"key":"1316_CR5","doi-asserted-by":"crossref","unstructured":"Braun, G., Pokutta, S., Zink, D.: Inapproximability of combinatorial problems via small LPs and SDPs. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC), pp. 107\u2013116. ACM (2015)","DOI":"10.1145\/2746539.2746550"},{"key":"1316_CR6","doi-asserted-by":"crossref","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pp. 350\u2013359. IEEE (2013)","DOI":"10.1109\/FOCS.2013.45"},{"key":"1316_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali\u2013Adams relaxations. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of computing, pp. 283\u2013292. ACM (2009)","DOI":"10.1145\/1536414.1536455"},{"issue":"2","key":"1316_CR8","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"S Chawla","year":"2006","unstructured":"Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15(2), 94\u2013114 (2006)","journal-title":"Comput. Complex."},{"key":"1316_CR9","doi-asserted-by":"crossref","unstructured":"Cheeger, J., Kleiner, B., Naor, A.: A $$(\\log n)^{\\Omega (1)}$$ integrality gap for the sparsest cut SDP. In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201909), pp. 555\u2013564. IEEE (2009)","DOI":"10.1109\/FOCS.2009.47"},{"key":"1316_CR10","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de\u00a0Wolf, R.: Linear vs. semidefinite extended formulations: Exponential separation and strong lower bounds. In: Proceedings of STOC, pp. 95\u2013106 (2012)","DOI":"10.1145\/2213977.2213988"},{"key":"1316_CR11","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de\u00a0Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC), pp. 95\u2013106. ACM (2012)","DOI":"10.1145\/2213977.2213988"},{"key":"1316_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Talwar, K., Witmer, D.: Sparsest cut on bounded treewidth graphs: algorithms and hardness results. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of computing, pp. 281\u2013290. ACM (2013)","DOI":"10.1145\/2488608.2488644"},{"issue":"1","key":"1316_CR13","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/2629614","volume":"62","author":"SA Khot","year":"2015","unstructured":"Khot, S.A., Vishnoi, N.K.: The Unique Games Conjecture, integrality gap for cut problems and embeddability of negative-type metrics into $$\\ell _{1}$$. J. ACM (JACM) 62(1), 8 (2015)","journal-title":"J. ACM (JACM)"},{"key":"1316_CR14","doi-asserted-by":"publisher","unstructured":"Kothari, P.K., Meka, R., Raghavendra, P.: Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. In: Proceedings of STOC, pp. 590\u2013603. ACM, New York (2017). \n                    https:\/\/doi.org\/10.1145\/3055399.3055438","DOI":"10.1145\/3055399.3055438"},{"key":"1316_CR15","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Raghavendra, P., Steurer, D.: Lower bounds on the size of semidefinite programming relaxations. arXiv preprint \n                    arXiv:1411.6317\n                    \n                   (2014)","DOI":"10.1145\/2746539.2746599"},{"key":"1316_CR16","unstructured":"Pashkovich, K.: Extended formulations for combinatorial polytopes. Ph.D. thesis, Magdeburg Universit\u00e4t (2012)"},{"key":"1316_CR17","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. In: Proceedings of STOC, pp. 263\u2013272 (2014)","DOI":"10.1145\/2591796.2591834"},{"key":"1316_CR18","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear level Lasserre lower bounds for certain k-CSPs. In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science FOCS\u201908, pp. 593\u2013602. IEEE (2008)","DOI":"10.1109\/FOCS.2008.74"},{"issue":"6","key":"1316_CR19","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074\u20132097 (2000)","journal-title":"SIAM J. Comput."},{"key":"1316_CR20","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs (extended abstract). In: Proceedings of STOC, pp. 223\u2013228 (1988)","DOI":"10.1145\/62212.62232"},{"issue":"3","key":"1316_CR21","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). \n                    https:\/\/doi.org\/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-018-1316-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1316-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1316-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:24:05Z","timestamp":1589646245000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1316-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,25]]},"references-count":21,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["1316"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1316-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2018,8,25]]},"assertion":[{"value":"27 April 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}