{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:40:04Z","timestamp":1750196404299,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"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":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451103","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1056-1069","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A quasipolynomial (2 +\n            <i>\u03b5<\/i>\n            )-approximation for planar sparsest cut"],"prefix":"10.1145","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip N.","family":"Klein","sequence":"additional","affiliation":[{"name":"Brown University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jason","family":"Li","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384310"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1112406"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9283-6"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646145"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-07-00573-5"},{"key":"e_1_3_2_1_6_1","first-page":"37","article-title":"Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2)","volume":"5","author":"Arora S.","year":"2009","unstructured":"S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):Art. 5, 37, 2009.","journal-title":"Art."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130913328"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213980"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.79"},{"key":"e_1_3_2_1_11_1","first-page":"18","article-title":"Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2)","volume":"22","author":"Chawla S.","year":"2008","unstructured":"S. Chawla, A. Gupta, and H. R\u00e4cke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2):Art. 22, 18, 2008.","journal-title":"Art."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102417379"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.11.002"},{"key":"e_1_3_2_1_15_1","series-title":"LNCS","first-page":"137","volume-title":"APPROX","author":"E.","unstructured":"E. Chlamt\u00e1\\vc, R. Krauthgamer, and P. Raghavendra. Approximating sparsest cut in graphs of bounded treewidth. In APPROX, volume 6302 of LNCS, pages 124\u2013137. 2010."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"e_1_3_2_1_17_1","first-page":"290","volume-title":"STOC","author":"Gupta A.","year":"2013","unstructured":"A. Gupta, K. Talwar, and D. Witmer. On the non-uniform sparsest cut problem on bounded treewidth graphs. In STOC, pages 281\u2013290, 2013."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_1_20_1","first-page":"39","article-title":"The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics into $\\ell_1$. J. ACM, 62(1)","volume":"8","author":"Khot S. A.","year":"2015","unstructured":"S. A. Khot and N. K. Vishnoi. The unique games conjecture, integrability gap for cut problems and embeddability of negative-type metrics into $\\ell_1$. J. ACM, 62(1):Art. 8, 39, 2015.","journal-title":"Art."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89595"},{"key":"e_1_3_2_1_23_1","unstructured":"P. N. Klein and S. Mozes. Optimization algorithms for planar graphs \u2013 http:\/\/planarity.org\/."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200755"},{"key":"e_1_3_2_1_25_1","first-page":"108","volume-title":"FOCS","author":"Lee J. R.","year":"2006","unstructured":"J. R. Lee and A. Naor. $l_p$ metrics on the Heisenberg group and the Goemans-Linial conjecture. In FOCS, pages 99\u2013108, 2006."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116275.3116548"},{"key":"e_1_3_2_1_27_1","first-page":"254","volume-title":"STOC","author":"Lee J. R.","unstructured":"J. R. Lee and A. Sidiropoulos. On the geometry of graphs with a forbidden minor. In STOC, pages 245\u2013254. 2009."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2685-8"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90133-W"},{"key":"e_1_3_2_1_31_1","first-page":"575","volume-title":"STOC","author":"Naor A.","year":"2017","unstructured":"A. Naor and R. Young. The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of $\\sqrt\u0142og n$. In STOC, pages 564\u2013575, 2017."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2018.188.1.4"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167284"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811416"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01299746"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 24th Annual ACM Symposium on Theory of Computing","author":"Rao S.","year":"1992","unstructured":"S. Rao. Faster algorithms for finding small edge cuts in planar graphs (extended abstract). In S. R. Kosaraju, M. Fellows, A. Wigderson, and J. A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 229\u2013240. ACM, 1992."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":38,"alternative-id":["10.1145\/3406325.3451103","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451103","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}