{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:50Z","timestamp":1750694810781,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T00:00:00Z","timestamp":1718928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>\n            A\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            edit distance of a given sequence of parentheses\n            <jats:italic>S<\/jats:italic>\n            is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform\n            <jats:italic>S<\/jats:italic>\n            into a\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            sequence. We consider the threshold\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            edit distance problem, where the input is a sequence of parentheses\n            <jats:italic>S<\/jats:italic>\n            and a positive integer\n            <jats:italic>k<\/jats:italic>\n            , and the goal is to compute the\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            edit distance of\n            <jats:italic>S<\/jats:italic>\n            only if the distance is at most\n            <jats:italic>k<\/jats:italic>\n            , and otherwise report that the distance is larger than\n            <jats:italic>k<\/jats:italic>\n            . Backurs and Onak [PODS\u201916] showed that the threshold\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            edit distance problem can be solved in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>16<\/jats:sup>\n            ) time.\n          <\/jats:p>\n          <jats:p>\n            In this work, we design new algorithms for the threshold\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            edit distance problem which costs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>4.544184<\/jats:sup>\n            ) time with high probability or\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>4.853059<\/jats:sup>\n            ) deterministically. Our algorithms combine several new structural properties of the\n            <jats:sans-serif>Dyck<\/jats:sans-serif>\n            edit distance problem, a refined algorithm for fast (min, +) matrix product, and a careful modification of ideas used in Valiant\u2019s parsing algorithm.\n          <\/jats:p>","DOI":"10.1145\/3627539","type":"journal-article","created":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T21:30:58Z","timestamp":1697751058000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["An Improved Algorithm\u00a0for The\n            <i>k<\/i>\n            -Dyck Edit Distance Problem"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1859-8082","authenticated-orcid":false,"given":"Dvir","family":"Fried","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8357-2802","authenticated-orcid":false,"given":"Shay","family":"Golan","sequence":"additional","affiliation":[{"name":"Reichman University, Israel and University of Haifa, Herzliya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Berkeley, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3525-8314","authenticated-orcid":false,"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6912-5766","authenticated-orcid":false,"given":"Ely","family":"Porat","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7193-9432","authenticated-orcid":false,"given":"Tatiana","family":"Starikovskaya","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,21]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.16"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201022"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1388"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902304"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M112720X"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520057"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","unstructured":"Shucheng Chi Ran Duan Tianle Xie and Tianyi Zhang. 2022. Faster min-plus product for monotone instances. (2022) 1529\u20131542. DOI:DOI:10.1145\/3519935.3520057","DOI":"10.1145\/3519935.3520057"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/s0049-237x(08)72023-8"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.49"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Anita D\u00fcrr. 2023. Improved Bounds for Rectangular Monotone Min-Plus Product and Applications.","DOI":"10.2139\/ssrn.4187498"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_5"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.2000.4172"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.5555\/578595"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","unstructured":"Rajesh Jayaram and Barna Saha. 2017. Approximating language edit distance beyond fast matrix multiplication: Ultralinear grammars are where parsing becomes hard!. In Proceedings of the 44th International Colloquium on Automata Languages and Programming. 19:1\u201319:15. DOI:DOI:10.4230\/LIPIcs.ICALP.2017.19","DOI":"10.4230\/LIPIcs.ICALP.2017.19"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1844-9"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22993-0_38"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/505241.505242"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00007-y"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.011"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01551-9_14"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.71"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.17"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.35"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80046-8"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.2"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627539","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627539","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:04Z","timestamp":1750287004000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,21]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3627539"],"URL":"https:\/\/doi.org\/10.1145\/3627539","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,6,21]]},"assertion":[{"value":"2022-06-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}