{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T16:11:26Z","timestamp":1787760686016,"version":"build-2784847793"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100007937","name":"Peking University","doi-asserted-by":"publisher","award":["409864"],"award-info":[{"award-number":["409864"]}],"id":[{"id":"10.13039\/501100007937","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617713"],"award-info":[{"award-number":["CCF-1617713"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814603"],"award-info":[{"award-number":["CCF-1814603"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1814603"],"award-info":[{"award-number":["CCF-1814603"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1910588"],"award-info":[{"award-number":["CCF-1910588"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1750808"],"award-info":[{"award-number":["CCF-1750808"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617713"],"award-info":[{"award-number":["CCF-1617713"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1845349"],"award-info":[{"award-number":["CCF-1845349"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This paper studies linear and affine error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear\/affine insdel codes. Linear codes that can correct even a single deletion are limited to having an information rate at most [Formula: see text] (achieved by the trivial two fold repetition code). Previously, it was (erroneously) reported that more generally no nontrivial linear codes correcting [Formula: see text] deletions exist, i.e., that the [Formula: see text]-fold repetition codes and its rate of [Formula: see text] are basically optimal for any [Formula: see text]. We disprove this and show the existence of binary linear codes of length [Formula: see text] and rate just below [Formula: see text] capable of correcting [Formula: see text] insertions and deletions. This identifies rate [Formula: see text] as a sharp threshold for recovery from deletions for linear codes and reopens the quest for a better understanding of the capabilities of linear codes for correcting insertions\/deletions. We prove novel outer bounds and existential inner bounds for the rate vs. (edit) distance trade-off of linear insdel codes. We complement our existential results with an efficient synchronization-string-based transformation that converts any asymptotically good linear code for Hamming errors into an asymptotically good linear code for insdel errors. Last, we show that the [Formula: see text]-rate limitation does not hold for affine codes by giving an explicit affine code of rate [Formula: see text] which can efficiently correct a constant fraction of insdel errors.<\/jats:p>","DOI":"10.1137\/21m142798x","type":"journal-article","created":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T12:48:25Z","timestamp":1686314905000},"page":"748-778","source":"Crossref","is-referenced-by-count":12,"title":["Efficient Linear and Affine Codes for Correcting Insertions\/Deletions"],"prefix":"10.1137","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8972-1749","authenticated-orcid":true,"given":"Kuan","family":"Cheng","sequence":"first","affiliation":[{"name":"Center on Frontiers of Computing Studies, Computer Science Department, Peking University."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Johns Hopkins University, Baltimore, MD 21218 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,6,6]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"N. Alon , \nJ. Edmonds , and \nM. Luby , Linear time erasure codes with nearly optimal recovery, in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, pp. 512\u2013519.","DOI":"10.1109\/SFCS.1995.492581"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"K. A. S. Abdel-Ghaffar , \nH. C. Ferreira , and \nL. Cheng , On linear and cyclic codes for correcting deletions, in Proceedings of the 2007 IEEE International Symposium on Information Theory (ISIT), 2007, pp. 851\u2013855.","DOI":"10.1109\/ISIT.2007.4557110"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2621044"},{"key":"ref5","author":"Brakensiek J.","year":"2015","journal-title":"CoRR"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2746566"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"K. Cheng , \nB. Haeupler , \nX. Li , \nA. Shahrasbi , and \nK. Wu , Synchronization strings: Efficient and fast deterministic constructions over small alphabets, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.","DOI":"10.1137\/1.9781611975482.132"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"K. Cheng , \nZ. Jin , \nX. Li , and \nK. Wu , Deterministic document exchange protocols, and almost optimal binary codes for edit errors, in Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, IEEE Computer Society, 2018, pp. 200\u2013211.","DOI":"10.1109\/FOCS.2018.00028"},{"key":"ref9","series-title":"LIPIcs Leibniz Int. Proc. Inform. 132","first-page":"37:1","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)","author":"Cheng K.","year":"2019"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"V. Guruswami , \nB. Haeupler , and \nA. Shahrasbi , Optimally resilient codes for list-decoding from insertions and deletions, in Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, 2020, pp. 524\u2013537.","DOI":"10.1145\/3357713.3384262"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2659765"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"B. Haeupler , Optimal document exchange and new codes for insertions and deletions, in Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019, pp. 334\u2013347.","DOI":"10.1109\/FOCS.2019.00029"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2841936"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"B. Haeupler , \nA. Rubinstein , and \nA. Shahrasbi , Near-linear time insertion-deletion codes and   \\((1+\\epsilon)\\)  -approximating edit distance via indexing, in Proceedings of the ACM Symposium on Theory of Computing (STOC), 2019, pp. 697\u2013708.","DOI":"10.1145\/3313276.3316371"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"B. Haeupler  and \nA. Shahrasbi , Synchronization strings: Codes for insertions and deletions approaching the Singleton bound, in Proceedings of the 49th Annual ACM Symposium on Theory of Computing, ACM, 2017, pp. 33\u201346.","DOI":"10.1145\/3055399.3055498"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"B. Haeupler  and \nA. Shahrasbi , Synchronization strings: Explicit constructions, local decoding, and applications, in Proceedings of the 50th Annual ACM Symposium on Theory of Computing, ACM, New York, 2018, pp. 841\u2013854.","DOI":"10.1145\/3188745.3188940"},{"key":"ref18","unstructured":"B. Haeupler , \nA. Shahrasbi , and \nM. Sudan , Synchronization strings: List decoding for insertions and deletions, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2018, pp. 76:1\u201376:14."},{"key":"ref19","unstructured":"B. Haeupler , \nA. Shahrasbi , and \nE. Vitercik , Synchronization strings: Channel simulations and interactive coding for insertions and deletions, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2018, pp. 75:1\u201375:14."},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"T. Hayashi  and \nK. Yasunaga , On the list decodability of insertions and deletions, in Proceedings of the IEEE International Symposium on Information Theory (ISIT), IEEE, 2018, pp. 86\u201390.","DOI":"10.1109\/ISIT.2018.8437894"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/18.945244"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"J. Sima  and \nJ. Bruck , Optimal k-deletion correcting codes, in Proceedings of the IEEE International Symposium on Information Theory, 2019, pp. 847\u2013851.","DOI":"10.1109\/ISIT.2019.8849750"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/18.796406"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2777471"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M142798X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:49:47Z","timestamp":1787316587000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M142798X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,6]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/21M142798X"],"URL":"https:\/\/doi.org\/10.1137\/21m142798x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,6]]}}}