{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:11:31Z","timestamp":1787508691017,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":24,"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\/100014155","name":"Simons Foundation","doi-asserted-by":"publisher","award":["332622"],"award-info":[{"award-number":["332622"]}],"id":[{"id":"10.13039\/100014155","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Grantov\u00e1 Agentura \u00f0esk\u00e9 Republiky","award":["19-27871X"],"award-info":[{"award-number":["19-27871X"]}]},{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["616787"],"award-info":[{"award-number":["616787"]}],"id":[{"id":"10.13039\/100011199","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.3384307","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"699-712","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Constant factor approximations to edit distance on far input pairs in nearly linear time"],"prefix":"10.1145","author":[{"given":"Michal","family":"Kouck\u00fd","sequence":"first","affiliation":[{"name":"Charles University in Prague, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[{"name":"Rutgers 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","volume-title":"Towards Hardness of Approximation for Polynomial Time Problems. In 8th Innovations in Theoretical Computer Science Conference, ITCS","author":"Abboud Amir","year":"2017","unstructured":"Amir Abboud and Arturs Backurs . 2017 . Towards Hardness of Approximation for Polynomial Time Problems. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. 11 : 1-11 : 26. Amir Abboud and Arturs Backurs. 2017. Towards Hardness of Approximation for Polynomial Time Problems. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. 11 : 1-11 : 26."},{"key":"e_1_3_2_1_2_1","first-page":"59","volume-title":"Tight Hardness Results for LCS and Other Sequence Similarity Measures. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud , Arturs Backurs , and Virginia Vassilevska Williams . 2015 . Tight Hardness Results for LCS and Other Sequence Similarity Measures. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2015. 59 - 78 . Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. Tight Hardness Results for LCS and Other Sequence Similarity Measures. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2015. 59-78."},{"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","unstructured":"Alex Andoni. 2018. Simpler Constant-Factor Approximation to Edit Distance Problems. Manuscript ( 2018 ).  Alex Andoni. 2018. Simpler Constant-Factor Approximation to Edit Distance Problems. Manuscript ( 2018 )."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536444"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_1_8_1","first-page":"550","volume-title":"Proc. of the Annual IEEE Symp. on Found. of Comp. Sci., FOCS","author":"Bar-Yossef Z.","year":"2004","unstructured":"Z. Bar-Yossef , T.S. Jayram , R. Krauthgamer , and R. Kumar . 2004. Approximating edit distance eficiently . In Proc. of the Annual IEEE Symp. on Found. of Comp. Sci., FOCS 2004 . 550 - 559 . Z. Bar-Yossef, T.S. Jayram, R. Krauthgamer, and R. Kumar. 2004. Approximating edit distance eficiently. In Proc. of the Annual IEEE Symp. on Found. of Comp. Sci., FOCS 2004. 550-559."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780590"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109644"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.76"},{"key":"e_1_3_2_1_12_1","volume-title":"Mohammad Taghi Hajiaghayi, and Saeed Seddighin","author":"Boroujeni Mahdi","year":"2018","unstructured":"Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi , Mohammad Taghi Hajiaghayi, and Saeed Seddighin . 2018 . Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce ( extended version of ). ( 2018 ). Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. 2018. Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce (extended version of ). ( 2018 )."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384282"},{"key":"e_1_3_2_1_14_1","first-page":"79","volume-title":"Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS","author":"Bringmann Karl","year":"2015","unstructured":"Karl Bringmann and Marvin K\u00fcnnemann . 2015 . Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2015. 79 - 97 . Karl Bringmann and Marvin K\u00fcnnemann. 2015. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2015. 79-97."},{"key":"e_1_3_2_1_15_1","first-page":"979","volume-title":"Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS","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. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2018 . 979 - 990 . 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. In Prof. of the IEEE Annual Symp. on Found. of Comp. Sci., FOCS 2018. 979-990."},{"key":"e_1_3_2_1_16_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 http:\/\/arxiv.org\/abs\/ 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 http:\/\/arxiv.org\/abs\/ 1810.03664"},{"key":"e_1_3_2_1_17_1","volume-title":"Proc. of FSTTCS 2019 (LIPIcs)","volume":"150","author":"Chakraborty Diptarka","year":"2019","unstructured":"Diptarka Chakraborty , Debarati Das , and Michal Kouck\u00fd . 2019 . Approximate Online Pattern Matching in Sublinear Time . In Proc. of FSTTCS 2019 (LIPIcs) , Vol. 150 . 10: 1-10 : 15. Diptarka Chakraborty, Debarati Das, and Michal Kouck\u00fd. 2019. Approximate Online Pattern Matching in Sublinear Time. In Proc. of FSTTCS 2019 (LIPIcs), Vol. 150. 10: 1-10 : 15."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00070"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Szymon Grabowski. 2016. New tabulation and sparse dynamic programming based techniques for sequence similarity problems. Discrete Applied Mathematics 212 ( 2016 ) 96-103.  Szymon Grabowski. 2016. New tabulation and sparse dynamic programming based techniques for sequence similarity problems. Discrete Applied Mathematics 212 ( 2016 ) 96-103.","DOI":"10.1016\/j.dam.2015.10.040"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"e_1_3_2_1_21_1","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."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"}],"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.3384307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:13Z","timestamp":1750185673000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":24,"alternative-id":["10.1145\/3357713.3384307","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384307","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"}}]}}