Fetching the paper…
Reading the bibliography…
Locally decodable codes (LDC's) are error-correcting codes that allow recovery of individual message indices by accessing only a constant number of codeword indices.
A mathematical theory of communication
C. E. Shannon · 1948
Earlier work this paper cites.
Error detecting and error correcting codes
R. W. Hamming · 1950
Earlier work this paper cites.
Application of boolean algebra to switching circuit design and to error detection
David E Muller · 1954
Earlier work this paper cites.
A class of multiple-error-correcting codes and the decoding scheme
Irving S Reed · 1954
Earlier work this paper cites.
Binary codes capable of correcting deletions, insertions, and reversals
Vladimir I Levenshtein · 1966
Earlier work this paper cites.
Checking computations in polylogarithmic time
László Babai, Lance Fortnow, Leonid A Levin, and Mario Szegedy · 1991
Earlier work this paper cites.
Private information retrieval
Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan · 1998
Earlier work this paper cites.
Asymptotically good codes correcting insertions, deletions, and transpositions
Leonard J Schulman and David Zuckerman · 1999
Earlier work this paper cites.
On the efficiency of local decoding procedures for error-correcting codes
Jonathan Katz and Luca Trevisan · 2000
Earlier work this paper cites.
Lower bounds for linear locally decodable codes and private information retrieval
Oded Goldreich, Howard Karloff, Leonard J Schulman, and Luca Trevisan · 2002
Earlier work this paper cites.
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Iordanis Kerenidis and Ronald De Wolf · 2003
Earlier work this paper cites.
Some applications of coding theory in computational complexity
Luca Trevisan · 2004
Cited alongside, same era.
Improved lower bounds for locally decodable codes and private information retrieval
Stephanie Wehner and Ronald De Wolf · 2005
Cited alongside, same era.
New lower bounds for general locally decodable codes
David Woodruff · 2007
Cited alongside, same era.
Insertion, deletion codes with feature-based embedding: a new paradigm for watermark synchronization with applications to speech watermarking
David J Coumou and Gaurav Sharma · 2008
Cited alongside, same era.
3-query locally decodable codes of subexponential length
Klim Efremenko · 2009
Cited alongside, same era.
A survey of results for deletion channels and related synchronization channels
Michael Mitzenmacher · 2009
Coding over sets for dna storage
Andreas Lenz, Paul H Siegel, Antonia Wachter-Zeh, and Eitan Yaakobi · 2019
Later among the works it cites.
Locally decodable/correctable codes for insertions and deletions
Alexander R Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, and Minshen Zhu · 2020
Later among the works it cites.
Locally decodable codes with randomized encoding
Kuan Cheng, Xin Li, and Yu Zheng · 2020
Later among the works it cites.
Private and resource-bounded locally decodable codes for insertions and deletions
Alexander R. Block and Jeremiah Blocki · 2021
Later among the works it cites.
Synchronization strings and codes for insertions and deletions—a survey
Bernhard Haeupler and Amirbehshad Shahrasbi · 2021
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Locally decodable codes
Sergey Yekhanin · 2012
Cited alongside, same era.
Locally decodable codes for edit distance
Rafail Ostrovsky and Anat Paskin-Cherniavsky · 2015
Cited alongside, same era.
Codes in the damerau distance for dna storage
Ryan Gabrys, Eitan Yaakobi, and Olgica Milenkovic · 2016
Cited alongside, same era.
Coding for interactive communication correcting insertions and deletions
Mark Braverman, Ran Gelles, Jieming Mao, and Rafail Ostrovsky · 2017
Cited alongside, same era.
Synchronization strings: codes for insertions and deletions approaching the singleton bound
Bernhard Haeupler and Amirbehshad Shahrasbi · 2017
Cited alongside, same era.
Alex Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu · 2022
Later among the works it cites.
Exponential lower bounds for locally decodable and correctable codes for insertions and deletions
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu · 2022
Later among the works it cites.
The zero-rate threshold for adversarial bit-deletions is less than 1/2
Venkatesan Guruswami, Xiaoyu He, and Ray Li · 2022
Later among the works it cites.
A near-cubic lower bound for 3-query locally decodable codes from semirandom csp refutation
Omar Alrabiah, Venkatesan Guruswami, Pravesh K Kothari, and Peter Manohar · 2023
Closest in time.
An exponential lower bound for linear 3-query locally correctable codes
Pravesh K Kothari and Peter Manohar · 2023
Closest in time.