{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T15:40:50Z","timestamp":1772466050817,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":31,"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":["CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808, CCF-1814603"],"award-info":[{"award-number":["CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, NSF CAREER award CCF-1750808, CCF-1814603"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Alfred P. Sloan Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384262","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:11Z","timestamp":1624916891000},"page":"524-537","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Optimally resilient codes for list-decoding from insertions and deletions"],"prefix":"10.1145","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3381-0459","authenticated-orcid":false,"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Amirbehshad","family":"Shahrasbi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2008.4595172"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188816"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2746566"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch133"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2621044"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975000"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.132"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00028"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Kuan Cheng Zhengzhong Jin Xin Li and Ke Wu. 2019. Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. In International Colloquium on Automata Languages and Programming (ICALP). Kuan Cheng Zhengzhong Jin Xin Li and Ke Wu. 2019. Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes. In International Colloquium on Automata Languages and Programming (ICALP).","DOI":"10.1109\/FOCS.2018.00028"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Vlado Dan\u010d\u00edk and Mike Paterson. 1995. Upper bounds for the expected length of a longest common subsequence of two binary sequences. Random Structures & Algorithms 6 4 ( 1995 ) 449-458. Vlado Dan\u010d\u00edk and Mike Paterson. 1995. Upper bounds for the expected length of a longest common subsequence of two binary sequences. Random Structures & Algorithms 6 4 ( 1995 ) 449-458.","DOI":"10.1002\/rsa.3240060408"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541373"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.41"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2659765"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488715"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00029"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of the Annual Symposium on Theory of Computing (STOC). 697-708","author":"Haeupler Bernhard","year":"2019","unstructured":"Bernhard Haeupler , Aviad Rubinstein , and Amirbehshad Shahrasbi . 2019 . Nearlinear time insertion-deletion codes and (1+)-approximating edit distance via indexing . In Proceedings of the Annual Symposium on Theory of Computing (STOC). 697-708 . Bernhard Haeupler, Aviad Rubinstein, and Amirbehshad Shahrasbi. 2019. Nearlinear time insertion-deletion codes and (1+)-approximating edit distance via indexing. In Proceedings of the Annual Symposium on Theory of Computing (STOC). 697-708."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055498"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188940"},{"key":"e_1_3_2_1_20_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP). 76 : 1-76 : 14","author":"Haeupler Bernhard","year":"2018","unstructured":"Bernhard Haeupler , Amirbehshad Shahrasbi , and Madhu Sudan . 2018 . Synchronization Strings: List Decoding for Insertions and Deletions. In 45th International Colloquium on Automata, Languages, and Programming (ICALP). 76 : 1-76 : 14 . Bernhard Haeupler, Amirbehshad Shahrasbi, and Madhu Sudan. 2018. Synchronization Strings: List Decoding for Insertions and Deletions. In 45th International Colloquium on Automata, Languages, and Programming (ICALP). 76 : 1-76 : 14."},{"key":"e_1_3_2_1_21_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP). 75 : 1-75 : 14","author":"Haeupler Bernhard","year":"2018","unstructured":"Bernhard Haeupler , Amirbehshad Shahrasbi , and Ellen Vitercik . 2018 . Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. In 45th International Colloquium on Automata, Languages, and Programming (ICALP). 75 : 1-75 : 14 . Bernhard Haeupler, Amirbehshad Shahrasbi, and Ellen Vitercik. 2018. Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions. In 45th International Colloquium on Automata, Languages, and Programming (ICALP). 75 : 1-75 : 14."},{"key":"e_1_3_2_1_22_1","volume-title":"On the List Decodability of Insertions and Deletions. In 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 86-90","author":"Hayashi Tomohiro","year":"2018","unstructured":"Tomohiro Hayashi and Kenji Yasunaga . 2018 . On the List Decodability of Insertions and Deletions. In 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 86-90 . Tomohiro Hayashi and Kenji Yasunaga. 2018. On the List Decodability of Insertions and Deletions. In 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 86-90."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Marcos Kiwi Martin Loebl and Ji\u0159\u00ed Matou\u0161ek. 2005. Expected length of the longest common subsequence for large alphabets. Advances in Mathematics 197 2 ( 2005 ) 480-498. Marcos Kiwi Martin Loebl and Ji\u0159\u00ed Matou\u0161ek. 2005. Expected length of the longest common subsequence for large alphabets. Advances in Mathematics 197 2 ( 2005 ) 480-498.","DOI":"10.1016\/j.aim.2004.10.012"},{"key":"e_1_3_2_1_24_1","unstructured":"Vladimir Levenshtein. 1965. Binary codes capable of correcting deletions insertions and reversals. Doklady Akademii Nauk SSSR 163 4 ( 1965 ) 845-848. Vladimir Levenshtein. 1965. Binary codes capable of correcting deletions insertions and reversals. Doklady Akademii Nauk SSSR 163 4 ( 1965 ) 845-848."},{"key":"e_1_3_2_1_25_1","volume-title":"Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime. arXiv preprint arXiv","author":"Liu Shu","year":"1909","unstructured":"Shu Liu , Ivan Tjuawinata , and Chaoping Xing . 2019. Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime. arXiv preprint arXiv : 1909 . 03426 ( 2019 ). Shu Liu, Ivan Tjuawinata, and Chaoping Xing. 2019. Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime. arXiv preprint arXiv: 1909. 03426 ( 2019 )."},{"key":"e_1_3_2_1_26_1","volume-title":"List Decoding of Insertion and Deletion Codes. arXiv preprint arXiv","author":"Liu Shu","year":"1906","unstructured":"Shu Liu , Ivan Tjuawinata , and Chaoping Xing . 2019. List Decoding of Insertion and Deletion Codes. arXiv preprint arXiv : 1906 . 09705 ( 2019 ). Shu Liu, Ivan Tjuawinata, and Chaoping Xing. 2019. List Decoding of Insertion and Deletion Codes. arXiv preprint arXiv: 1906. 09705 ( 2019 )."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516519"},{"key":"e_1_3_2_1_28_1","volume-title":"A survey of errorcorrecting codes for channels with symbol synchronization errors","author":"Mercier Hugues","year":"2010","unstructured":"Hugues Mercier , Vijay K Bhargava , and Vahid Tarokh . 2010. A survey of errorcorrecting codes for channels with symbol synchronization errors . IEEE Communications Surveys & Tutorials 12, 1 ( 2010 ). Hugues Mercier, Vijay K Bhargava, and Vahid Tarokh. 2010. A survey of errorcorrecting codes for channels with symbol synchronization errors. IEEE Communications Surveys & Tutorials 12, 1 ( 2010 )."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher. 2009. A survey of results for deletion channels and related synchronization channels. Probability Surveys 6 ( 2009 ) 1-33. Michael Mitzenmacher. 2009. A survey of results for deletion channels and related synchronization channels. Probability Surveys 6 ( 2009 ) 1-33.","DOI":"10.1214\/08-PS141"},{"key":"e_1_3_2_1_30_1","volume-title":"Schulman and David Zuckerman","author":"Leonard","year":"1999","unstructured":"Leonard J. Schulman and David Zuckerman . 1999 . Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE transactions on information theory 45, 7 ( 1999 ), 2552-2557. Leonard J. Schulman and David Zuckerman. 1999. Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE transactions on information theory 45, 7 ( 1999 ), 2552-2557."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Neil J. A Sloane. 2002. On single-deletion-correcting codes. Codes and designs 10 ( 2002 ) 273-291. Neil J. A Sloane. 2002. On single-deletion-correcting codes. Codes and designs 10 ( 2002 ) 273-291.","DOI":"10.1515\/9783110198119.273"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2777471"}],"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.3384262","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384262","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.3384262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":31,"alternative-id":["10.1145\/3357713.3384262","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384262","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"}}]}}