Fetching the paper…
Reading the bibliography…
Locally Decodable Codes (LDCs) are error-correcting codes $C:\Sigma^n\rightarrow \Sigma^m$ with super-fast decoding algorithms.
Binary codes capable of correcting deletions, insertions and reversals
Vladimir Iosifovich Levenshtein · 1965
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.
Algebraic methods for interactive proof systems
Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan · 1992
Earlier work this paper cites.
Self-testing/correcting with applications to numerical problems
Manuel Blum, Michael Luby, and Ronitt Rubinfeld · 1993
Earlier work this paper cites.
A new approach to information theory
Richard J. Lipton · 1994
Earlier work this paper cites.
Designing programs that check their work
Manuel Blum and Sampath Kannan · 1995
Earlier work this paper cites.
Private information retrieval
Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan · 1998
Earlier work this paper cites.
Pseudorandom generators without the XOR lemma (abstract)
Madhu Sudan, Luca Trevisan, and Salil P. Vadhan · 1999
Earlier work this paper cites.
Asymptotically good codes correcting insertions, deletions, and transpositions
L. J. Schulman and D. 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.
On single-deletion-correcting codes
N.J.A. Sloane · 2002
Earlier work this paper cites.
Error correction against computationally bounded adversaries
Yan Ding, Parikshit Gopalan, and Richard Lipton · 2004
Earlier work this paper cites.
A survey on private information retrieval (column: Computational complexity)
William I. Gasarch · 2004
Earlier work this paper cites.
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Iordanis Kerenidis and Ronald de Wolf · 2004
Earlier work this paper cites.
Some applications of coding theory in computational complexity
Luca Trevisan · 2004
Earlier work this paper cites.
Expected length of the longest common subsequence for large alphabets
Jiri Matousek Marcos Kiwi, Martin Loebl · 2005
Earlier work this paper cites.
Optimal error correction against computationally bounded noise
Silvio Micali, Chris Peikert, Madhu Sudan, and David A. Wilson · 2005
Earlier work this paper cites.
Improved lower bounds for locally decodable codes and private information retrieval
Stephanie Wehner and Ronald de Wolf · 2005
Earlier work this paper cites.
Robust pcps of proximity, shorter pcps, and applications to coding
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan · 2006
Earlier work this paper cites.
Lower bounds for linear locally decodable codes and private information retrieval
Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, and Luca Trevisan · 2006
Earlier work this paper cites.
Private locally decodable codes
Rafail Ostrovsky, Omkant Pandey, and Amit Sahai · 2007
Earlier work this paper cites.
New lower bounds for general locally decodable codes
David P. Woodruff · 2007
Earlier work this paper cites.
A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs
Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf · 2008
Earlier work this paper cites.
Public-key locally-decodable codes
Brett Hemenway and Rafail Ostrovsky · 2008
Earlier work this paper cites.
A survey of results for deletion channels and related synchronization channels
Michael Mitzenmacher · 2008
Earlier work this paper cites.
Towards 3-query locally decodable codes of subexponential length
Sergey Yekhanin · 2008
Earlier work this paper cites.
A survey of error-correcting codes for channels with symbol synchronization errors
Hugues Mercier, Vijay K. Bhargava, and Vahid Tarokh · 2010
Cited alongside, same era.
Matching vector codes
Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin · 2011
Cited alongside, same era.
Public key locally decodable codes with short keys
Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, and Mary Wootters · 2011
Cited alongside, same era.
3-query locally decodable codes of subexponential length
Klim Efremenko · 2012
Cited alongside, same era.
Three-query locally decodable codes with higher correctness require exponential length
Anna Gál and Andrew Mills · 2012
Cited alongside, same era.
A quadratic lower bound for three-query linear locally decodable codes over any field
David P. Woodruff · 2012
Cited alongside, same era.
Synchronization strings: List decoding for insertions and deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, and Madhu Sudan · 2018
Later among the works it cites.
Synchronization strings: Highly efficient deterministic constructions over small alphabets
Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, and Ke Wu · 2019
Later among the works it cites.
Block edit errors with transpositions: Deterministic document exchange protocols and almost optimal binary codes
Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu · 2019
Later among the works it cites.
A lower bound for relaxed locally decodable codes
Tom Gur and Oded Lachish · 2019
Later among the works it cites.
Polynomial time decodable codes for the binary deletion channel
Venkatesan Guruswami and Ray Li · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Locally decodable codes
Sergey Yekhanin · 2012
Cited alongside, same era.
Error-correcting data structures
Victor Chen, Elena Grigorescu, and Ronald de Wolf · 2013
Cited alongside, same era.
Local correctability of expander codes
Brett Hemenway, Rafail Ostrovsky, and Mary Wootters · 2015
Cited alongside, same era.
Locally decodable codes for edit distance
Rafail Ostrovsky and Anat Paskin-Cherniavsky · 2015
Cited alongside, same era.
Tight lower bounds for linear 2-query lccs over finite fields
Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, and Amir Shpilka · 2016
Cited alongside, same era.
Optimal rate code constructions for computationally simple channels
Venkatesan Guruswami and Adam Smith · 2016
Cited alongside, same era.
Optimal document exchange and new codes for insertions and deletions
Bernhard Haeupler · 2019
Later among the works it cites.
Near-linear time insertion-deletion codes and (1+ ϵ \epsilon )-approximating edit distance via indexing
Bernhard Haeupler, Aviad Rubinstein, and Amirbehshad Shahrasbi · 2019
Later among the works it cites.
On list decoding of insertion and deletion errors
Shu Liu, Ivan Tjuawinata, and Chaoping Xing · 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.
Combinatorial lower bounds for 3-query ldcs
Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal · 2020
Later among the works it cites.
On Locally Decodable Codes in Resource Bounded Channels
Jeremiah Blocki, Shubhang Kulkarni, and Samson Zhou · 2020
Later among the works it cites.
Relaxed locally correctable codes with nearly-linear block length and constant query complexity
Alessandro Chiesa, Tom Gur, and Igor Shinkar · 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.
Optimally resilient codes for list-decoding from insertions and deletions
Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi · 2020
Later among the works it cites.
Relaxed locally correctable codes
Tom Gur, Govind Ramnarayan, and Ron Rothblum · 2020
Later among the works it cites.
Relaxed locally correctable codes with improved parameters
Vahid R. Asadi and Igor Shinkar · 2021
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.
Relaxed locally correctable codes in computationally bounded channels
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, and Samson Zhou · 2021
Later among the works it cites.
Random access dna memory using boolean search in an archival file storage system
James L. Banal, Tyson R. Shepherd, Joseph Berleant, Hellen Huang, Miguel Reyes, Cheri M. Ackerman, Paul C. Blainey, and Mark Bathe · 2021
Later among the works it cites.
Efficient linear and affine codes for correcting insertions/deletions
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, and Xin Li · 2021
Later among the works it cites.
Efficient document exchange and error correcting codes with asymmetric information
Kuan Cheng and Xin Li · 2021
Later among the works it cites.
A structural theorem for local algorithms with applications to coding, testing, and privacy
Marcel Dall’Agnol, Tom Gur, and Oded Lachish · 2021
Later among the works it cites.
On the power of relaxed local decoding algorithms
Tom Gur and Oded Lachish · 2021
Later among the works it cites.
Synchronization strings and codes for insertions and deletions – a survey, 2021
Bernhard Haeupler and Amirbehshad Shahrasbi · 2021
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 Kothari, and Peter Manohar · 2022
Closest in time.
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
Closest in time.