{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:32Z","timestamp":1750220972593,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Robert N. Noyce Family Faculty Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1618280, CCF-1814603, CCF-1527110, CCF-1750808"],"award-info":[{"award-number":["CCF-1618280, CCF-1814603, CCF-1527110, CCF-1750808"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316371","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"697-708","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Near-linear time insertion-deletion codes and (1+\n            <i>\u03b5<\/i>\n            )-approximating edit distance via indexing"],"prefix":"10.1145","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}]},{"given":"Amirbehshad","family":"Shahrasbi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_2_1_2_1","unstructured":"Amir Abboud Thomas Dueholm Hansen Virginia Vassilevska Williams and Ryan Williams. 2016.  Amir Abboud Thomas Dueholm Hansen Virginia Vassilevska Williams and Ryan Williams. 2016."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796292"},{"key":"e_1_3_2_1_6_1","unstructured":"Alexandr Andoni and Robert Krauthgamer. 2008.  Alexandr Andoni and Robert Krauthgamer. 2008."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_30"},{"key":"e_1_3_2_1_8_1","unstructured":"Alexandr Andoni Robert Krauthgamer and Krzysztof Onak. 2010.  Alexandr Andoni Robert Krauthgamer and Krzysztof Onak. 2010."},{"volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 377\u2013386","author":"Polylogarithmic","key":"e_1_3_2_1_9_1"},{"key":"e_1_3_2_1_10_1","unstructured":"Alexandr Andoni and Krzysztof Onak. 2012.  Alexandr Andoni and Krzysztof Onak. 2012."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Approximating edit distance in near-linear time. SIAM J. Comput. 41 6 (2012) 1635\u20131648.  Approximating edit distance in near-linear time. SIAM J. Comput. 41 6 (2012) 1635\u20131648.","DOI":"10.1137\/090767182"},{"key":"e_1_3_2_1_12_1","unstructured":"Arturs Backurs and Piotr Indyk. 2015.  Arturs Backurs and Piotr Indyk. 2015."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_1_14_1","unstructured":"Ziv Bar-Yossef TS Jayram Robert Krauthgamer and Ravi Kumar. 2004.  Ziv Bar-Yossef TS Jayram Robert Krauthgamer and Ravi Kumar. 2004."},{"volume-title":"Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on. IEEE, 550\u2013559","author":"Approximating","key":"e_1_3_2_1_15_1"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109644"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.76"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175349"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00096"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310567"},{"key":"e_1_3_2_1_22_1","unstructured":"V\u00e1clav Chv\u00e1tal David A. Klarner and Donald E. Knuth. 1972.  V\u00e1clav Chv\u00e1tal David A. Klarner and Donald E. Knuth. 1972."},{"volume-title":"Technical Report. Computer Science Department","author":"Selected","key":"e_1_3_2_1_23_1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_24"},{"volume-title":"The Complexity of Problems in P Given Correlated Instances. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017","year":"2017","author":"Goldwasser Shafi","key":"e_1_3_2_1_25_1"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541373"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2659765"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055498"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188940"},{"volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP).","year":"2018","author":"Haeupler Bernhard","key":"e_1_3_2_1_31_1"},{"volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP). 75:1\u201375:14","year":"2018","author":"Haeupler Bernhard","key":"e_1_3_2_1_32_1"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.27"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"e_1_3_2_1_36_1","unstructured":"William Kuszmaul. 2019.  William Kuszmaul. 2019."},{"volume-title":"Approximating Edit Distance Between Pseudorandom Strings. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1165\u20131180","author":"Efficiently","key":"e_1_3_2_1_37_1"},{"key":"e_1_3_2_1_38_1","unstructured":"Gad M Landau Eugene W Myers and Jeanette P Schmidt. 1998.  Gad M Landau Eugene W Myers and Jeanette P Schmidt. 1998."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Incremental string comparison. SIAM J. Comput. 27 2 (1998) 557\u2013582.   Incremental string comparison. SIAM J. Comput. 27 2 (1998) 557\u2013582.","DOI":"10.1137\/S0097539794264810"},{"key":"e_1_3_2_1_40_1","unstructured":"Vladimir Levenshtein. 1965. Binary codes capable of correcting deletions insertions and reversals. Doklady Akademii Nauk SSSR 163 4 (1965) 845\u2013848.  Vladimir Levenshtein. 1965. Binary codes capable of correcting deletions insertions and reversals. Doklady Akademii Nauk SSSR 163 4 (1965) 845\u2013848."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_3_2_1_42_1","unstructured":"Aviad Rubinstein. 2018. Approximating Edit Distance. https:\/\/theorydish.blog\/ 2018\/07\/20\/approximatingeditdistance\/.  Aviad Rubinstein. 2018. Approximating Edit Distance. https:\/\/theorydish.blog\/ 2018\/07\/20\/approximatingeditdistance\/."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796406"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365734"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316371","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316371","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":45,"alternative-id":["10.1145\/3313276.3316371","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316371","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}