{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T13:59:11Z","timestamp":1787061551004,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":48,"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":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1652303"],"award-info":[{"award-number":["1652303"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384300","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"657-670","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Does preprocessing help in fast sequence comparisons?"],"prefix":"10.1145","author":[{"given":"Elazar","family":"Goldenberg","sequence":"first","affiliation":[{"name":"Academic College of Tel Aviv-Yaffo, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barna","family":"Saha","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, 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.4230\/LIPIcs.ITCS.2017.11"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.8"},{"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.1109\/FOCS.2017.12"},{"key":"e_1_3_2_1_5_1","unstructured":"Amir Abboud and Virginia Vassilevska Williams. 2019. Personal communication.  Amir Abboud and Virginia Vassilevska Williams. 2019. Personal communication."},{"key":"e_1_3_2_1_6_1","unstructured":"Alexandr Andoni. 2019. Simpler Constant-Factor Approximation to Edit Distance Problems. In preparation.  Alexandr Andoni. 2019. Simpler Constant-Factor Approximation to Edit Distance Problems. In preparation."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644196"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780590"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109644"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.15"},{"key":"e_1_3_2_1_16_1","volume-title":"Finding monotone patterns in sublinear time. CoRR, abs\/1910.01749","author":"Ben-Eliezer Omri","year":"2019","unstructured":"Omri Ben-Eliezer , Cl\u00e9ment L. Canonne , Shoham Letzter , and Erik Waingarten . 2019. Finding monotone patterns in sublinear time. CoRR, abs\/1910.01749 ( 2019 ), arxiv:1910.01749. arxiv:1910.01749 Omri Ben-Eliezer, Cl\u00e9ment L. Canonne, Shoham Letzter, and Erik Waingarten. 2019. Finding monotone patterns in sublinear time. CoRR, abs\/1910.01749 (2019), arxiv:1910.01749. arxiv:1910.01749"},{"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.5555\/2884435.2884567"},{"key":"e_1_3_2_1_19_1","volume-title":"Constant-factor approximation of near-linear edit distance in near-linear time. CoRR, abs\/1904.05390","author":"Brakensiek Joshua","year":"2019","unstructured":"Joshua Brakensiek and Aviad Rubinstein . 2019. Constant-factor approximation of near-linear edit distance in near-linear time. CoRR, abs\/1904.05390 ( 2019 ), arxiv:1904.05390. arxiv:1904.05390 Joshua Brakensiek and Aviad Rubinstein. 2019. Constant-factor approximation of near-linear edit distance in near-linear time. CoRR, abs\/1904.05390 (2019), arxiv:1904.05390. arxiv:1904.05390"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.79"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00096"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897577"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.34"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a011"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.1"},{"key":"e_1_3_2_1_27_1","volume-title":"Sublinear Algorithms for Gap Edit Distance. FOCS, abs\/1910.00901","author":"Goldenberg Elazar","year":"2019","unstructured":"Elazar Goldenberg , Robert Krauthgamer , and Barna Saha . 2019. Sublinear Algorithms for Gap Edit Distance. FOCS, abs\/1910.00901 ( 2019 ), arxiv:1910.00901. arxiv:1910.00901 Elazar Goldenberg, Robert Krauthgamer, and Barna Saha. 2019. Sublinear Algorithms for Gap Edit Distance. FOCS, abs\/1910.00901 (2019), arxiv:1910.00901. arxiv:1910.00901"},{"key":"e_1_3_2_1_28_1","volume-title":"Optimal Document Exchange and New Codes for Insertions and Deletions. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS.","author":"Haeupler Bernhard","year":"2019","unstructured":"Bernhard Haeupler . 2019 . Optimal Document Exchange and New Codes for Insertions and Deletions. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS. Bernhard Haeupler. 2019. Optimal Document Exchange and New Codes for Insertions and Deletions. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316371"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.72"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004","author":"Indyk Piotr","year":"2004","unstructured":"Piotr Indyk . 2004 . Approximate Nearest Neighbor under edit distance via product metrics . In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004 , New Orleans, Louisiana, USA , January 11-14, 2004. 646\u2013650. http:\/\/dl.acm.org\/citation.cfm?id=982792.982889 Piotr Indyk. 2004. Approximate Nearest Neighbor under edit distance via product metrics. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004. 646\u2013650. http:\/\/dl.acm.org\/citation.cfm?id=982792.982889"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-56024-6_5"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_56"},{"key":"e_1_3_2_1_34_1","volume-title":"Saks","author":"Kouck\u00fd Michal","year":"2019","unstructured":"Michal Kouck\u00fd and Michael E . Saks . 2019 . Constant factor approximations to edit distance on far input pairs in nearly linear time. CoRR , abs\/1904.05459 (2019), arxiv:1904.05459. arxiv:1904.05459 Michal Kouck\u00fd and Michael E. Saks. 2019. Constant factor approximations to edit distance on far input pairs in nearly linear time. CoRR, abs\/1904.05459 (2019), arxiv:1904.05459. arxiv:1904.05459"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"e_1_3_2_1_37_1","first-page":"707","article-title":"Binary Codes Capable of Correcting Deletions, Insertions and Reversals","volume":"10","author":"Levenshtein VI","year":"1966","unstructured":"VI Levenshtein . 1966 . Binary Codes Capable of Correcting Deletions, Insertions and Reversals . Soviet Physics Doklady , 10 (1966), 707 . VI Levenshtein. 1966. Binary Codes Capable of Correcting Deletions, Insertions and Reversals. Soviet Physics Doklady, 10 (1966), 707.","journal-title":"Soviet Physics Doklady"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2309131"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840446"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20840"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284322"},{"key":"e_1_3_2_1_42_1","unstructured":"Aviad Rubinstein. 2018. Approximating Edit Distance. https:\/\/theorydish.blog\/2018\/07\/20\/approximating-edit-distance\/  Aviad Rubinstein. 2018. Approximating Edit Distance. https:\/\/theorydish.blog\/2018\/07\/20\/approximating-edit-distance\/"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_3_2_1_44_1","volume-title":"Approximation Algorithms for LCS and LIS with Truly Improved Running Times. In FOCS","author":"Rubinstein Aviad","year":"2019","unstructured":"Aviad Rubinstein , Saeed Seddighin , Zhao Song , and Xiaorui Sun . 2019 . Approximation Algorithms for LCS and LIS with Truly Improved Running Times. In FOCS 2019. To appear. Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun. 2019. Approximation Algorithms for LCS and LIS with Truly Improved Running Times. In FOCS 2019. To appear."},{"key":"e_1_3_2_1_45_1","volume-title":"Reducing approximate Longest Common Subsequence to approximate Edit Distance. CoRR, abs\/1904.05451","author":"Rubinstein Aviad","year":"2019","unstructured":"Aviad Rubinstein and Zhao Song . 2019. Reducing approximate Longest Common Subsequence to approximate Edit Distance. CoRR, abs\/1904.05451 ( 2019 ), arxiv:1904.05451. arxiv:1904.05451 Aviad Rubinstein and Zhao Song. 2019. Reducing approximate Longest Common Subsequence to approximate Edit Distance. CoRR, abs\/1904.05451 (2019), arxiv:1904.05451. arxiv:1904.05451"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/130942152"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"}],"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.3384300","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":48,"alternative-id":["10.1145\/3357713.3384300","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384300","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"}}]}}