{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:48Z","timestamp":1781077728806,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":13,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF GRFP"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384282","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"685-698","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Constant-factor approximation of near-linear edit distance in near-linear time"],"prefix":"10.1145","author":[{"given":"Joshua","family":"Brakensiek","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109644"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.76"},{"key":"e_1_3_2_1_8_1","volume-title":"Saks","author":"Chakraborty Diptarka","year":"2018","unstructured":"Diptarka Chakraborty , Debarati Das , Elazar Goldenberg , Michal Kouck\u00fd , and Michael E . Saks . 2018 . Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR , abs\/1810.03664 (2018), arxiv:1810.03664. arxiv:1810.03664 Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Kouck\u00fd, and Michael E. Saks. 2018. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time. CoRR, abs\/1810.03664 (2018), arxiv:1810.03664. arxiv:1810.03664"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.34"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Michal Kouck\u1ef3 and Michael E Saks. 2019. Constant factor approximations to edit distance on far input pairs in nearly linear time. arXiv preprint arXiv:1904.05459.  Michal Kouck\u1ef3 and Michael E Saks. 2019. Constant factor approximations to edit distance on far input pairs in nearly linear time. arXiv preprint arXiv:1904.05459.","DOI":"10.1145\/3357713.3384307"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284322"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Aviad Rubinstein and Zhao Song. 2020. Reducing approximate Longest Common Subsequence to approximate Edit Distance. SODA.  Aviad Rubinstein and Zhao Song. 2020. Reducing approximate Longest Common Subsequence to approximate Edit Distance. SODA.","DOI":"10.1137\/1.9781611975994.98"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384282","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":13,"alternative-id":["10.1145\/3357713.3384282","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384282","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}