{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T00:08:06Z","timestamp":1755907686374,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":16,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Army Research Laboratory","doi-asserted-by":"publisher","award":["W911NF2410052"],"award-info":[{"award-number":["W911NF2410052"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["2337832, 2218678, 2114269, 2347322, 1652303, 1909046, 2112533, 2217058"],"award-info":[{"award-number":["2337832, 2218678, 2114269, 2347322, 1652303, 1909046, 2112533, 2217058"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,17]]},"DOI":"10.1145\/3626183.3660265","type":"proceedings-article","created":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T18:23:04Z","timestamp":1717525384000},"page":"293-295","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Brief Announcement: Upper and Lower Bounds for Edit Distance in Space-Efficient MPC"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2232-4279","authenticated-orcid":false,"given":"Debarati","family":"Das","sequence":"first","affiliation":[{"name":"Pennsylvania State University, State College, Pennsylvania, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9860-5558","authenticated-orcid":false,"given":"Jacob","family":"Gilbert","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4842-0533","authenticated-orcid":false,"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[{"name":"Saarland Informatics Campus, Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6494-3839","authenticated-orcid":false,"given":"Barna","family":"Saha","sequence":"additional","affiliation":[{"name":"University of California, San Diego, San Diego, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Tight Hardness Results for LCS and Other Sequence Similarity Measures. In FOCS","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015a. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In FOCS 2015. 59--78."},{"key":"e_1_3_2_1_2_1","volume-title":"Virginia Vassilevska Williams, and Huacheng Yu","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. 2015b. Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. In STOC. 41--50."},{"key":"e_1_3_2_1_3_1","volume-title":"Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. In FOCS","author":"Andoni Alexandr","year":"2010","unstructured":"Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. 2010. Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. In FOCS 2010. 377--386."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219066"},{"key":"e_1_3_2_1_5_1","series-title":"SIAM J. Comput. (2018), 1087--1097","volume-title":"Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)","author":"Backurs Arturs","unstructured":"Arturs Backurs and Piotr Indyk. 2018. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput. (2018), 1087--1097."},{"key":"e_1_3_2_1_6_1","volume-title":"Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce. In SODA 2018","author":"Boroujeni Mahdi","year":"2018","unstructured":"Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. 2018. Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce. In SODA 2018, 2018. 1170--1189."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323205"},{"key":"e_1_3_2_1_8_1","volume-title":"Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In FOCS","author":"Bringmann Karl","year":"2014","unstructured":"Karl Bringmann. 2014. Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. In FOCS 2014. IEEE Computer Society, 661--670."},{"key":"e_1_3_2_1_9_1","first-page":"1102","article-title":"Almost-optimal sublinear-time edit distance in the low distance regime","volume":"2022","author":"Bringmann Karl","year":"2022","unstructured":"Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos. 2022. Almost-optimal sublinear-time edit distance in the low distance regime. In STOC, 2022. 1102--1115.","journal-title":"STOC"},{"key":"e_1_3_2_1_10_1","first-page":"79","article-title":"Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping","volume":"2015","author":"Bringmann Karl","year":"2015","unstructured":"Karl Bringmann and Marvin K\u00fcnnemann. 2015. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In FOCS, 2015. 79--97.","journal-title":"FOCS"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378574"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari Fabian Kuhn and Jara Uitto. 2019. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In FOCS. 1650--1663.","DOI":"10.1109\/FOCS.2019.00097"},{"key":"e_1_3_2_1_13_1","volume-title":"ISAAC","author":"Goodrich Michael T.","year":"2011","unstructured":"Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, Searching, and Simulation in the MapReduce Framework. In ISAAC 2011. 374--383."},{"key":"e_1_3_2_1_14_1","first-page":"1654","article-title":"Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence","volume":"2019","author":"Hajiaghayi MohammadTaghi","year":"2019","unstructured":"MohammadTaghi Hajiaghayi, Saeed Seddighin, and Xiaorui Sun. 2019. Massively Parallel Approximation Algorithms for Edit Distance and Longest Common Subsequence. In SODA, 2019. 1654--1672.","journal-title":"SODA"},{"key":"e_1_3_2_1_15_1","volume-title":"Equivalence Classes and Conditional Hardness in Massively Parallel Computations. CoRR","author":"Nanongkai Danupon","year":"2020","unstructured":"Danupon Nanongkai and Michele Scquizzato. 2020. Equivalence Classes and Conditional Hardness in Massively Parallel Computations. CoRR, Vol. abs\/2001.02191 (2020)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"}],"event":{"name":"SPAA '24: 36th ACM Symposium on Parallelism in Algorithms and Architectures","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"],"location":"Nantes France","acronym":"SPAA '24"},"container-title":["Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3660265","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626183.3660265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T16:24:25Z","timestamp":1755879865000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3660265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":16,"alternative-id":["10.1145\/3626183.3660265","10.1145\/3626183"],"URL":"https:\/\/doi.org\/10.1145\/3626183.3660265","relation":{},"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2024-06-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}