{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:09Z","timestamp":1750220529134,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":44,"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"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1336\/16"],"award-info":[{"award-number":["1336\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["852870"],"award-info":[{"award-number":["852870"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451071","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1601-1614","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The metric relaxation for\n            <i>0<\/i>\n            -extension admits an\n            <i>\n              \u03a9(log\n              <sup>2\/3<\/sup>\n              k)\n            <\/i>\n            gap"],"prefix":"10.1145","author":[{"given":"Roy","family":"Schwartz","sequence":"first","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitzan","family":"Tur","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Small Lifts of Expander Graphs are Expanding. ArXiv, abs\/1311.3268","author":"Agarwal Naman","year":"2013","unstructured":"Naman Agarwal, Alexandra Kolla, and Vivek Madan. 2013. Small Lifts of Expander Graphs are Expanding. ArXiv, abs\/1311.3268, 2013."},{"volume-title":"Integer Programming and Combinatorial Optimization","author":"Angelidakis Haris","key":"e_1_3_2_1_2_1","unstructured":"Haris Angelidakis, Yury Makarychev, and Pasin Manurangsi. 2017. An Improved Integrality Gap for the C\\u alinescu-Karloff-Rabani Relaxation for Multiway Cut. In Integer Programming and Combinatorial Optimization. Springer International Publishing. Pages 39\u201350."},{"key":"e_1_3_2_1_3_1","first-page":"1087","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '04","author":"Archer Aaron","year":"2004","unstructured":"Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and \\'Eva Tardos. 2004. Approximate Classification via Earthmover Metrics. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '04. Pages 1079\u20131087."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1605"},{"key":"e_1_3_2_1_5_1","first-page":"28","volume-title":"Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08","author":"Arora Sanjeev","unstructured":"Sanjeev Arora, Subhash A. Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. 2008. Unique Games on Expanding Constraint Graphs Are Easy: Extended Abstract. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08. Pages 21\u201328."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548477"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"volume-title":"Integer Programming and Combinatorial Optimization","author":"B\u00e9rczi Krist\u00f3f","key":"e_1_3_2_1_8_1","unstructured":"Krist\u00f3f B\u00e9rczi, Karthekeyan Chandrasekaran, Tam\u00e1s Kir\u00e1ly, and Vivek Madan. 2019. Improving the Integrality Gap for Multiway Cut. In Integer Programming and Combinatorial Optimization. Springer International Publishing. Pages 115\u2013127."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0029-7"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1045521"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.158"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2019.09.012"},{"key":"e_1_3_2_1_13_1","first-page":"2","article-title":"Approximation Algorithms for the 0-Extension Problem","volume":"34","author":"Gruia","year":"2005","unstructured":"Gruia C\\u alinescu, Howard Karloff, and Yuval Rabani. 2005. Approximation Algorithms for the 0-Extension Problem. SIAM J. Comput., 34, 2, 2005. Pages 358\u2013372.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_2_1_14_1","first-page":"3","article-title":"An Improved Approximation Algorithm for MULTIWAY CUT","volume":"60","author":"Gruia","year":"2000","unstructured":"Gruia C\\u alinescu, Howard J. Karloff, and Yuval Rabani. 2000. An Improved Approximation Algorithm for MULTIWAY CUT. J. Comput. Syst. Sci., 60, 3, 2000. Pages 564\u2013574.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101396937"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0668-2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/06065430X"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"volume-title":"Graph Theory (Graduate Texts in Mathematics)","author":"Diestel Reinhard","key":"e_1_3_2_1_19_1","unstructured":"Reinhard Diestel. 2005. Graph Theory (Graduate Texts in Mathematics). Springer."},{"key":"e_1_3_2_1_20_1","first-page":"265","volume-title":"Symposium on Discrete Algorithms. SODA '03","author":"Fakcharoenphol Jittat","year":"2003","unstructured":"Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. 2003. An Improved Approximation Algorithm for the 0-Extension Problem. In Symposium on Discrete Algorithms. SODA '03. Pages 257\u2013265."},{"key":"e_1_3_2_1_21_1","first-page":"2007","article-title":"A tight bound on approximating arbitrary metrics by tree metrics","volume":"69","author":"Fakcharoenphol Jittat","year":"2007","unstructured":"Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. 2007. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69, 3, October, 2007. Pages 485\u2013497.","journal-title":"J. Comput. System Sci."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00065-X"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-03-11812-8"},{"volume-title":"Proceedings of 37th Conference on Foundations of Computer Science. FOCS '96. Pages 12\u201320","author":"Alan","key":"e_1_3_2_1_24_1","unstructured":"Alan M. Frieze and Ravi Kannan. 1996. The regularity lemma and approximation schemes for dense problems. In Proceedings of 37th Conference on Foundations of Computer Science. FOCS '96. Pages 12\u201320."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00111-1"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335397"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764938"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1030.0086"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685671"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0154"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"e_1_3_2_1_34_1","volume-title":"Extending Lipschitz functions via random metric partitions. Inventiones mathematicae, 160, 2","author":"Lee James","year":"2004","unstructured":"James Lee and Assaf Naor. 2004. Extending Lipschitz functions via random metric partitions. Inventiones mathematicae, 160, 2, 2004."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20304"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374379"},{"volume-title":"Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. FOCS '13. Pages 529\u2013537","author":"Marcus A.","key":"e_1_3_2_1_38_1","unstructured":"A. Marcus, D. A. Spielman, and N. Srivastava. 2013. Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. FOCS '13. Pages 529\u2013537."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.75"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384231"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979732147X"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Ryan O'Donnell and Xinyu Wu. 2020. Explicit near-fully X-Ramanujan graphs.","DOI":"10.1109\/FOCS46700.2020.00101"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a005"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591866"}],"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.3451071","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451071","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.3451071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":44,"alternative-id":["10.1145\/3406325.3451071","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451071","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"}}]}}