On the efficiency of local decoding procedures for error-correcting codes

By J. Katz, Luca Trevisan. Symposium on the Theory of Computing, 2000

336 citations recorded by the source corpus.

jkatz s. olumbia.edu. Department of Computer S ien e, Columbia University. Work supported in part by a DoD NDSEG Fellowship. y lu a s. olumbia.edu. Department of Computer S ien e, Columbia University. time (or whose reading devi e is subje t to errors). For example, the data stored in musi CDs and in CD-ROMs is en oded using Reed-Solomon odes. In appli ations to data storage (and also in appli ations to data transmission) a message is typi ally divided into small blo ks, and then ea h blo k is en oded separately. This allows eÆ ient retrieval of

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/2b1375d39479f4f83a6f337791abe5d206b044f6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

On the Locality of Codeword Symbols (2011, background): “These codes were introduced in [6] and developed further in e.”
Robust pcps of proximity, shorter pcps and applications to coding (2004, background): “[10] Bogdanov, A., and Trevisan, L. Lower bounds for testing bipartiteness in dense graphs.”
Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval (2002, methodology): “Katz and Trevisan [23] have shown an intimate relation between such codes and information-theoretic PIR.”
A Survey on Private Information Retrieval (Column: Computational Complexity) (2004, background): “PIR’s that are allowed to make errors but with low probability [42, 43].”
Information-Theoretic Private Information Retrieval: A Unified Construction (2001, background): “As observed in [18], a 1-private k-server PIR protocol with query length α and answer length β gives rise to a locally decodable code of length k · 2 over the alphabet Σ = {0, 1}β : A string x ∈ {0, 1}n is encoded by concatenating the answers of all servers on all possible queries, where x is viewed”
Batch codes and their applications (2004, methodology): “Using the more general terminology of [18], this is a (q; q; 1=2)smooth code.”
Introduction to Property Testing (2017, background): “In contrast, by [179], there exist no (non-relaxed) locally decodable codes of T2-nearly linear length.”
Robust Information-Theoretic Private Information Retrieval (2002, background): “Lower bounds for locally decodable codes were introduced in [40, 36, 52, 25, 41, 64, 57].”