{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:50Z","timestamp":1781077730267,"version":"3.54.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T00:00:00Z","timestamp":1620864000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF CAREER","award":["CCF-1053605"],"award-info":[{"award-number":["CCF-1053605"]}]},{"name":"NSF BIGDATA","award":["IIS-1546108"],"award-info":[{"award-number":["IIS-1546108"]}]},{"name":"NSF AF:Medium","award":["CCF-1161365"],"award-info":[{"award-number":["CCF-1161365"]}]},{"name":"DARPA GRAPHS\/AFOSR","award":["FA9550-12-1-0423"],"award-info":[{"award-number":["FA9550-12-1-0423"]}]},{"name":"DARPA SIMPLEX"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            The\n            <jats:italic>edit distance<\/jats:italic>\n            between two strings is defined as the smallest number of\n            <jats:italic>insertions<\/jats:italic>\n            ,\n            <jats:italic>deletions<\/jats:italic>\n            , and\n            <jats:italic>substitutions<\/jats:italic>\n            that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is \u201cone of the biggest unsolved problems in the field of combinatorial pattern matching\u201d\u00a0[37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            quantum algorithm that approximates the edit distance within a larger constant factor.\n          <\/jats:p>\n          <jats:p>\n            Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to\n            <jats:italic>metric estimation<\/jats:italic>\n            and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.\n          <\/jats:p>","DOI":"10.1145\/3456807","type":"journal-article","created":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T20:05:42Z","timestamp":1620936342000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7246-251X","authenticated-orcid":false,"given":"Mahdi","family":"Boroujeni","sequence":"first","affiliation":[{"name":"Sharif University of Technology, Tehran, Iran"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Soheil","family":"Ehsani","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Ghodsi","sequence":"additional","affiliation":[{"name":"Sharif University of Technology, Iran, and Institute for Research in Fundamental Sciences (IPM), Rocquencourt, Tehran, Iran"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammadtaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saeed","family":"Seddighin","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, Illinois, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,5,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1826"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496864"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716530"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344434"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Alexandr Andoni and Negev Shekel Nosatzki. 2020. Edit distance in near-linear time: It\u2019s a constant factor. arxiv:cs.DS\/2005.07678  Alexandr Andoni and Negev Shekel Nosatzki. 2020. Edit distance in near-linear time: It\u2019s a constant factor. arxiv:cs.DS\/2005.07678","DOI":"10.1109\/FOCS46700.2020.00096"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219066"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109644"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258548"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.18"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175346"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381188"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323205"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"e_1_2_1_19_1","unstructured":"Joshua Brakensiek Moses Charikar and Aviad Rubinstein. 2020. A simple sublinear algorithm for gap edit distance. arxiv:cs.DS\/2007.14368  Joshua Brakensiek Moses Charikar and Aviad Rubinstein. 2020. A simple sublinear algorithm for gap edit distance. arxiv:cs.DS\/2007.14368"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384282"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00096"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422823"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a011"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/050644719"},{"key":"e_1_2_1_26_1","unstructured":"Alireza Farhadi MohammadTaghi HajiAghayi Aviad Rubinstein and Saeed Seddighin. 2020. Asymmetric streaming algorithms for edit distance and LCS. arxiv:cs.DS\/2002.11342  Alireza Farhadi MohammadTaghi HajiAghayi Aviad Rubinstein and Saeed Seddighin. 2020. Asymmetric streaming algorithms for edit distance and LCS. arxiv:cs.DS\/2002.11342"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.81.5442"},{"key":"e_1_2_1_28_1","unstructured":"Edward Farhi Jeffrey Goldstone Sam Gutmann and Michael Sipser. 1999. Invariant quantum algorithms for insertion into an ordered list. arxiv:quant-ph\/9901059  Edward Farhi Jeffrey Goldstone Sam Gutmann and Michael Sipser. 1999. Invariant quantum algorithms for insertion into an ordered list. arxiv:quant-ph\/9901059"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00070"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384300"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316371"},{"key":"e_1_2_1_33_1","unstructured":"MohammadTaghi HajiAghayi Silvio Lattanzi Saeed Seddighin and Cliff Stein. 2019. MapReduce meets fine-grained complexity: MapReduce algorithms for APSP matrix multiplication 3-SUM and beyond. arxiv:cs.DS\/1905.01748  MohammadTaghi HajiAghayi Silvio Lattanzi Saeed Seddighin and Cliff Stein. 2019. MapReduce meets fine-grained complexity: MapReduce algorithms for APSP matrix multiplication 3-SUM and beyond. arxiv:cs.DS\/1905.01748"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310535"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00010-8"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055460"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627923"},{"key":"e_1_2_1_39_1","unstructured":"Shagun Jhaver Latifur Khan and Bhavani Thuraisingham. 2014. Calculating edit distance for large sets of string pairs using MapReduce. Paper presented at ASE International Conference on Big Data.  Shagun Jhaver Latifur Khan and Bhavani Thuraisingham. 2014. Calculating edit distance for large sets of string pairs using MapReduce. Paper presented at ASE International Conference on Big Data."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00112"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384307"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/060660126"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-014-2285-5"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/279082.279125"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989505"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.31"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384240"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9826-8"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/211390"},{"key":"e_1_2_1_52_1","unstructured":"Aran Nayebi and Virginia Vassilevska Williams. 2014. Quantum algorithms for shortest paths problems in structured instances. arxiv:quant-ph\/1410.6220  Aran Nayebi and Virginia Vassilevska Williams. 2014. Quantum algorithms for shortest paths problems in structured instances. arxiv:quant-ph\/1410.6220"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284322"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00071"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3374857.3374870"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456807","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3456807","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:31:26Z","timestamp":1750195886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456807"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,13]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3456807"],"URL":"https:\/\/doi.org\/10.1145\/3456807","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,13]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}