{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:29:56Z","timestamp":1780054196414,"version":"3.54.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1617713, CCF-1845349"],"award-info":[{"award-number":["CCF-1617713, CCF-1845349"]}]},{"name":"59th Annual IEEE Symposium on Foundations of Computer Science"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            We study two basic problems regarding edit errors, document exchange and error correcting codes. Here, two parties try to exchange two strings with length roughly\n            <jats:italic>n<\/jats:italic>\n            and edit distance at most\n            <jats:italic>k<\/jats:italic>\n            , or one party tries to send a string of length\n            <jats:italic>n<\/jats:italic>\n            to another party through a channel that can introduce at most\n            <jats:italic>k<\/jats:italic>\n            edit errors. The goal is to use the least amount of communication or redundancy possible. Both problems have been extensively studied for decades, and in this article, we focus on deterministic document exchange protocols and binary codes for insertions and deletions (insdel codes). It is known that for small\n            <jats:italic>k<\/jats:italic>\n            (e.g.,\n            <jats:italic>k<\/jats:italic>\n            \u2264 n\/4 ), in both problems the optimal communication or redundancy size is \u0398 (\n            <jats:italic>k<\/jats:italic>\n            log n\/k). In particular, this implies the existence of binary codes that can correct \u03b5 fraction of edit errors with rate 1-\u0398 (\u03b5 log 1\/\u03b5 )). However, known constructions are far from achieving these bounds.\n          <\/jats:p>\n          <jats:p>\n            In this article, we significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with communication complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n\/k<\/jats:italic>\n            . This significantly improves the previous best-known deterministic protocol, which has communication complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            +\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) [\n            <jats:xref ref-type=\"bibr\">4<\/jats:xref>\n            ]. For binary insdel codes, we obtain the following results:\n            <jats:list list-type=\"ordered\">\n              <jats:list-item>\n                <jats:label>(1)<\/jats:label>\n                <jats:p>\n                  An explicit binary insdel code with redundancy\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>k<\/jats:italic>\n                  log\n                  <jats:sup>2<\/jats:sup>\n                  n\/k). In particular this implies an explicit family of binary insdel codes that can correct \u03b5 fraction of insertions and deletions with rate 1-O(\u03b5 log\n                  <jats:sup>2<\/jats:sup>\n                  (1\/\u03b5))=1-O\u0303(\u03b5). This significantly improves the previous best-known result, which only achieves rate 1-O\u0303(\u221a \u03b5) [\n                  <jats:xref ref-type=\"bibr\">14<\/jats:xref>\n                  ], [\n                  <jats:xref ref-type=\"bibr\">15<\/jats:xref>\n                  ], and is optimal up to a log (1\/\u03b5 factor.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:label>(2)<\/jats:label>\n                <jats:p>\n                  An explicit binary insdel code with redundancy\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>k<\/jats:italic>\n                  log\n                  <jats:italic>n<\/jats:italic>\n                  ). This significantly improves the previous best-known result of Reference [\n                  <jats:xref ref-type=\"bibr\">6<\/jats:xref>\n                  ], which only works for constant\n                  <jats:italic>k<\/jats:italic>\n                  and has redundancy\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>k<\/jats:italic>\n                  <jats:sup>2<\/jats:sup>\n                  log\n                  <jats:italic>k<\/jats:italic>\n                  log\n                  <jats:italic>n<\/jats:italic>\n                  ); and that of Reference [\n                  <jats:xref ref-type=\"bibr\">4<\/jats:xref>\n                  ], which has redundancy\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>k<\/jats:italic>\n                  <jats:sup>2<\/jats:sup>\n                  +\n                  <jats:italic>k<\/jats:italic>\n                  log\n                  <jats:sup>2<\/jats:sup>\n                  <jats:italic>n<\/jats:italic>\n                  ). Our code has optimal redundancy for\n                  <jats:italic>k<\/jats:italic>\n                  \u2264 n\n                  <jats:sup>1-\u03b1<\/jats:sup>\n                  , any constant 0&lt; \u03b1 &lt; 1. This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters\n                  <jats:italic>k<\/jats:italic>\n                  .\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>\n            In obtaining our results, we introduce several new techniques. Most notably, we introduce the notion of\n            <jats:italic>\u03b5-self-matching hash functions<\/jats:italic>\n            and\n            <jats:italic>\u03b5-synchronization hash functions<\/jats:italic>\n            . We believe our techniques can have further applications in the literature.\n          <\/jats:p>","DOI":"10.1145\/3561046","type":"journal-article","created":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T12:20:53Z","timestamp":1665058853000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Deterministic Document Exchange Protocols and Almost Optimal Binary Codes for Edit Errors"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8972-1749","authenticated-orcid":false,"given":"Kuan","family":"Cheng","sequence":"first","affiliation":[{"name":"Center on Frontiers of Computing Studies, Peking University, Beijing, P.R. China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2233-3768","authenticated-orcid":false,"given":"Zhengzhong","family":"Jin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9408-2451","authenticated-orcid":false,"given":"Xin","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2756-8750","authenticated-orcid":false,"given":"Ke","family":"Wu","sequence":"additional","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,17]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01277956"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_3_5_2","article-title":"Efficient deterministic single round document exchange for edit distance","author":"Belazzougui Djamal","year":"2015","unstructured":"Djamal Belazzougui. 2015. Efficient deterministic single round document exchange for edit distance. arXiv preprint arXiv:1511.09229 (2015).","journal-title":"arXiv preprint arXiv:1511.09229"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.15"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2746566"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch133"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2621044"},{"key":"e_1_3_3_10_2","volume-title":"Proceedings of the 48th IEEE Annual Annual ACM SIGACT Symposium on Theory of Computing","author":"Chakraborty Diptarka","year":"2016","unstructured":"Diptarka Chakraborty, Elazar Goldenberg, and Michal Kouck\u00fd. 2016. Low distortion embedding from edit to Hamming distance using coupling. In Proceedings of the 48th IEEE Annual Annual ACM SIGACT Symposium on Theory of Computing. ACM."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.132"},{"key":"e_1_3_3_12_2","first-page":"197","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Cormode Graham","year":"2000","unstructured":"Graham Cormode, Mike Paterson, Suleyman Cenk Sahinalp, and Uzi Vishkin. 2000. Communication complexity of document exchange. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, 197\u2013206."},{"key":"e_1_3_3_13_2","first-page":"504","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"De Anindya","year":"2010","unstructured":"Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. 2010. Improved pseudorandom generators for depth 2 circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer Berlin, 504\u2013517."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1006\/jnth.1996.0147"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541373"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2659765"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00029"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055498"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188940"},{"issue":"1","key":"e_1_3_3_20_2","first-page":"871","article-title":"Algebraic geometry codes","volume":"1","author":"H\u00f8holdt Tom","year":"1998","unstructured":"Tom H\u00f8holdt, Jacobus H. Van Lint, and Ruud Pellikaan. 1998. Algebraic geometry codes. Handb. Coding Theor. 1, Part 1 (1998), 871\u2013961.","journal-title":"Handb. Coding Theor."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2005.1498448"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_56"},{"issue":"8","key":"e_1_3_3_24_2","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions, and reversals","volume":"10","author":"Levenshtein Vladimir I.","year":"1966","unstructured":"Vladimir I. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. Sov. Phys. Dokl. 10, 8 (1966), 707\u2013710.","journal-title":"Sov. Phys. Dokl."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2010.020110.00079"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185373"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.796406"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.945244"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3028702"},{"key":"e_1_3_3_30_2","first-page":"288","article-title":"Code correcting single asymmetric errors(binary code correcting single asymmetric errors)","volume":"26","author":"Tenengolts G. M.","year":"1965","unstructured":"G. M. Tenengolts and R. R. Varshamov. 1965. Code correcting single asymmetric errors(binary code correcting single asymmetric errors). Avtomatika I Telemekhanika 26 (1965), 288\u2013292.","journal-title":"Avtomatika I Telemekhanika"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561046","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3561046","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3561046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:15Z","timestamp":1750182555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,17]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3561046"],"URL":"https:\/\/doi.org\/10.1145\/3561046","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,17]]},"assertion":[{"value":"2021-08-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}