{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T03:33:33Z","timestamp":1758080013401,"version":"3.44.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2025,9,5]]},"abstract":"<jats:p>Local decoding enables fast recovery of individual symbols of a message, even in the presence of errors. Locally decodable codes that can withstand Hamming errors are foundational in theoretical computer science, with deep connections to program checking, probabilistically checkable proofs, private information retrieval, and data structures.<\/jats:p>\n          <jats:p>More recently, the literature has expanded to address a much more challenging type of errors: insertions and deletions. These synchronization errors may cause misalignment in the data, and are especially relevant to emerging applications in DNA storage technologies.<\/jats:p>\n          <jats:p>In this article, we survey recent advances on local decoding in the presence of synchronization errors, highlight key techniques, and state several open problems.<\/jats:p>","DOI":"10.1145\/3767145.3767151","type":"journal-article","created":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T16:23:13Z","timestamp":1758039793000},"page":"56-75","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["SIGACT News Complexity Theory Column 126\n            <b>Locally Decodable Codes for Insertions and Deletions<\/b>"],"prefix":"10.1145","volume":"56","author":[{"given":"Elena","family":"Grigorescu","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,16]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"99","volume-title":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","author":"Alwen Jo\u00ebl","year":"2018","unstructured":"[ABP18] Jo\u00ebl Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained space complexity. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 99--130. Springer, 2018."},{"key":"e_1_2_1_2_1","first-page":"1438","volume-title":"STOC","author":"Alrabiah Omar","year":"2023","unstructured":"[AGKM23] Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation. In STOC, pages 1438--1448. ACM, 2023."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_4_1","unstructured":"[AS21] Vahid R. Asadi and Igor Shinkar. Relaxed locally correctable codes with improved parameters. In Nikhil Bansal Emanuela Merelli and James Worrell editors ICALP volume 198 of LIPIcs pages 18:1--18:12 2021."},{"key":"e_1_2_1_5_1","first-page":"1841","volume-title":"ISIT","author":"Alexander","year":"2021","unstructured":"[BB21] Alexander R. Block and Jeremiah Blocki. Private and resource-bounded locally decodable codes for insertions and deletions. In ISIT, pages 1841--1846. IEEE, 2021."},{"key":"e_1_2_1_6_1","series-title":"LIPIcs","first-page":"1","volume-title":"CCC","author":"Block Alexander R.","year":"2023","unstructured":"[BBC+23] Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu. On Relaxed Locally Decodable Codes for Hamming and Insertion- Deletion Errors. In CCC, volume 264 of LIPIcs, pages 14:1--14:25, 2023."},{"key":"e_1_2_1_7_1","series-title":"LIPIcs","first-page":"1","volume-title":"FSTTCS","author":"Block Alexander R.","year":"2020","unstructured":"[BBG+20] Alexander R. Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, and Minshen Zhu. Locally decodable\/correctable codes for insertions and deletions. In FSTTCS, volume 182 of LIPIcs, pages 16:1--16:17, 2020."},{"key":"e_1_2_1_8_1","first-page":"739","volume-title":"FOCS","author":"Blocki Jeremiah","year":"2021","unstructured":"[BCG+21] Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu. Exponential lower bounds for locally decodable and correctable codes for insertions and deletions. In FOCS, pages 739--750. IEEE, 2021."},{"key":"e_1_2_1_9_1","first-page":"2414","volume-title":"ISIT","author":"Blocki Jeremiah","year":"2019","unstructured":"[BGGZ19] Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, and Samson Zhou. Relaxed locally correctable codes in computationally bounded channels. In ISIT, pages 2414--2418. IEEE, 2019."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_1_11_1","series-title":"LIPIcs","first-page":"1","volume-title":"RANDOM","author":"Bhattacharyya Arnab","year":"2017","unstructured":"[BGT17] Arnab Bhattacharyya, Sivakanth Gopi, and Avishay Tal. Lower bounds for 2-query lccs over large alphabet. In RANDOM, volume 81 of LIPIcs, pages 30:1--30:20. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2017."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.45"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"1272","DOI":"10.1038\/s41563-021-01021-3","article-title":"Random access dna memory using boolean search in an archival file storage system","volume":"20","author":"Banal James L.","year":"2021","unstructured":"[BSB+21] James L. Banal, Tyson R. Shepherd, Joseph Berleant, Hellen Huang, Miguel Reyes, Cheri M. Ackerman, Paul C. Blainey, and Mark Bathe. Random access dna memory using boolean search in an archival file storage system. Nature Materials, 20:1272--1280, 2021.","journal-title":"Nature Materials"},{"key":"e_1_2_1_15_1","first-page":"1395","volume-title":"Relaxed locally correctable codes with nearly-linear block length and constant query complexity","author":"Chiesa Alessandro","year":"2020","unstructured":"[CGS20] Alessandro Chiesa, Tom Gur, and Igor Shinkar. Relaxed locally correctable codes with nearly-linear block length and constant query complexity. In Shuchi Chawla, editor, SODA, pages 1395--1411. SIAM, 2020."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_17_1","volume-title":"Efficient document exchange and error correcting codes with asymmetric information","author":"Cheng Kuan","year":"2020","unstructured":"[CL20] Kuan Cheng and Xin Li. Efficient document exchange and error correcting codes with asymmetric information, 2020."},{"key":"e_1_2_1_18_1","volume-title":"Locally decodable codes with randomized encoding. CoRR, abs\/2001.03692","author":"Cheng Kuan","year":"2020","unstructured":"[CLZ20] Kuan Cheng, Xin Li, and Yu Zheng. Locally decodable codes with randomized encoding. CoRR, abs\/2001.03692, 2020."},{"key":"e_1_2_1_19_1","first-page":"24","volume-title":"FOCS","author":"Cohen Gil","year":"2022","unstructured":"[CY22] Gil Cohen and Tal Yankovitz. Relaxed locally decodable and correctable codes: Beyond tensoring. In FOCS, pages 24--35. IEEE, 2022."},{"key":"e_1_2_1_20_1","unstructured":"[CY24] Gil Cohen and Tal Yankovitz. Asymptotically-good rlccs with (log n)(2+o(1)) queries. In Rahul Santhanam editor CCC volume 300 of LIPIcs pages 8:1--8:16 2024."},{"key":"e_1_2_1_21_1","first-page":"1651","volume-title":"SODA","author":"Dall'Agnol Marcel","year":"2021","unstructured":"[DGL21] Marcel Dall'Agnol, Tom Gur, and Oded Lachish. A structural theorem for local algorithms with applications to coding, testing, and privacy. In SODA, pages 1651--1665. SIAM, 2021."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/100804322"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772721"},{"key":"e_1_2_1_24_1","volume-title":"On sparse graphs with dense long paths. Technical report","author":"Erd\u00f6s Paul","year":"1975","unstructured":"[EGS75] Paul Erd\u00f6s, Ronald L. Graham, and Endre Szemeredi. On sparse graphs with dense long paths. Technical report, Stanford University, Stanford, CA, USA, 1975."},{"key":"e_1_2_1_25_1","first-page":"72","article-title":"A survey on private information retrieval (column: Computational complexity)","volume":"82","author":"Gasarch William I.","year":"2004","unstructured":"[Gas04] William I. Gasarch. A survey on private information retrieval (column: Computational complexity). Bulletin of the EATCS, 82:72--107, 2004.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_26_1","volume-title":"Manuscript","author":"Grigorescu Elena","year":"2025","unstructured":"[GKMM25] Elena Grigorescu, Vinayak Kumar, Peter Manohar, and Geoffrey Mon. Linear 3-query relaxed locally decodable codes are locally decodable. Manuscript, 2025."},{"key":"e_1_2_1_27_1","volume-title":"A lower bound for relaxed locally decodable codes. arXiv preprint arXiv:1904.08112","author":"Gur Tom","year":"2019","unstructured":"[GL19] Tom Gur and Oded Lachish. A lower bound for relaxed locally decodable codes. arXiv preprint arXiv:1904.08112, 2019."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1307834"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2020.v016a018"},{"key":"e_1_2_1_30_1","first-page":"752","volume-title":"STOC","author":"Gupta Meghal","year":"2024","unstructured":"[Gup24] Meghal Gupta. Constant query local decoding against deletions is impossible. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, STOC, pages 752--763. ACM, 2024."},{"key":"e_1_2_1_31_1","volume-title":"Synchronization strings and codes for insertionions and deletions -- a survey","author":"Haeupler Bernhard","year":"2021","unstructured":"[HS21] Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization strings and codes for insertionions and deletions -- a survey, 2021."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"e_1_2_1_33_1","first-page":"776","volume-title":"STOC","author":"Pravesh","year":"2024","unstructured":"[KM24a] Pravesh K. Kothari and Peter Manohar. An exponential lower bound for linear 3-query locally correctable codes. In STOC, pages 776--787. ACM, 2024."},{"key":"e_1_2_1_34_1","first-page":"1802","volume-title":"FOCS","author":"Pravesh","year":"2024","unstructured":"[KM24b] Pravesh K. Kothari and Peter Manohar. Exponential lower bounds for smooth 3-lccs and sharp bounds for designs. In FOCS, pages 1802--1845. IEEE, 2024."},{"key":"e_1_2_1_35_1","first-page":"1585","volume-title":"STOC","author":"Vinayak","year":"2024","unstructured":"[KM24c] Vinayak M. Kumar and Geoffrey Mon. Relaxed local correctability from local testing. In STOC, pages 1585--1593. ACM, 2024."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051093"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1025045"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2993749.2993761"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629416"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_41_1","volume-title":"Soviet physics doklady","author":"Levenshtein Vladimir I","year":"1966","unstructured":"[Lev66] Vladimir I Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady, volume 10(8), pages 707--710, 1966."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/646510.695010"},{"key":"e_1_2_1_43_1","first-page":"12","article-title":"A survey of error-correcting codes for channels with symbol synchronization errors","author":"Mercier Hugues","year":"2010","unstructured":"[MBT10] Hugues Mercier, Vijay K. Bhargava, and Vahid Tarokh. A survey of error-correcting codes for channels with symbol synchronization errors. IEEE Communications Surveys and Tutorials, 12, 2010.","journal-title":"IEEE Communications Surveys and Tutorials"},{"key":"e_1_2_1_44_1","first-page":"1","volume-title":"Algorithm Theory -- SWAT","author":"Mitzenmacher Michael","year":"2008","unstructured":"[Mit08] Michael Mitzenmacher. A survey of results for deletion channels and related synchronization channels. In Algorithm Theory -- SWAT 2008, volume 6, pages 1--3, 07 2008."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2024.3367748"},{"key":"e_1_2_1_46_1","first-page":"236","volume-title":"Information Theoretic Security","author":"Ostrovsky Rafail","year":"2015","unstructured":"[OP15] Rafail Ostrovsky and Anat Paskin-Cherniavsky. Locally decodable codes for edit distance. In Anja Lehmann and Stefan Wolf, editors, Information Theoretic Security, pages 236--249, Cham, 2015. Springer International Publishing."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_35"},{"key":"e_1_2_1_48_1","volume-title":"On single-deletion-correcting codes. arXiv: Combinatorics","author":"Sloane N.J.A.","year":"2002","unstructured":"[Slo02] N.J.A. Sloane. On single-deletion-correcting codes. arXiv: Combinatorics, 2002."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301397"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796406"},{"key":"e_1_2_1_51_1","volume-title":"Some applications of coding theory in computational complexity. CoRR, cs.CC\/0409044","author":"Trevisan Luca","year":"2004","unstructured":"[Tre04] Luca Trevisan. Some applications of coding theory in computational complexity. CoRR, cs.CC\/0409044, 2004."},{"issue":"1","key":"e_1_2_1_52_1","first-page":"1","article-title":"DNA punch cards for storing data on native DNA sequences via enzymatic nicking","volume":"11","author":"Tabatabaei S. Kasra","year":"2020","unstructured":"[TWA+20] S. Kasra Tabatabaei, Boya Wang, Nagendra Bala Murali Athreya, Behnam Enghiad, Alvaro Gonzalo Hernandez, Christopher J. Fields, Jean-Pierre Leburton, David Soloveichik, Huimin Zhao, and Olgica Mil. DNA punch cards for storing data on native DNA sequences via enzymatic nicking. Nature Communications, 11(1):1--10, December 2020.","journal-title":"Nature Communications"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3767145.3767151","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T16:23:28Z","timestamp":1758039808000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3767145.3767151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,5]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,5]]}},"alternative-id":["10.1145\/3767145.3767151"],"URL":"https:\/\/doi.org\/10.1145\/3767145.3767151","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2025,9,5]]},"assertion":[{"value":"2025-09-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}