Locally Decodable Codes

DOI10.1561/0400000030zbMath1278.94002OpenAlexW2242452602MaRDI QIDQ5891400

Sergey Yekhanin

Publication date: 15 January 2014

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000030

zbMATH Keywords

error-correcting codeslocally decodable codesefficient random-access retrievalhigh noise resilience

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65) Research exposition (monographs, survey articles) pertaining to information and communication theory (94-02) Decoding (94B35)

Related Items (35)

Sampling Correctors ⋮ Hermitian-lifted codes ⋮ Locality via Partially Lifted Codes ⋮ Relative generalized Hamming weights of \(q\)-ary Reed-Muller codes ⋮ Unnamed Item ⋮ Lifted projective Reed-Solomon codes ⋮ Locally verifiable signature and key aggregation ⋮ Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Succinct arguments for RAM programs via projection codes ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Unnamed Item ⋮ A novel elementary construction of matching vectors ⋮ Local correction of juntas ⋮ Unnamed Item ⋮ Relaxed Locally Correctable Codes ⋮ Locally Decodable Codes: A Brief Survey ⋮ Unnamed Item ⋮ Smooth and strong PCPs ⋮ Information-Theoretic Local Non-malleable Codes and Their Applications ⋮ Locally Decodable Codes ⋮ Locally recoverable codes from rational maps ⋮ High-entropy dual functions over finite fields and locally decodable codes ⋮ Locally decodable and updatable non-malleable codes and their applications ⋮ Public Key Locally Decodable Codes with Short Keys ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Identifying Generalized Reed-Muller Codewords by Quantum Queries ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Outlaw distributions and locally decodable codes ⋮ Conical Kakeya and Nikodym sets in finite fields ⋮ High-rate codes with sublinear-time decoding ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity ⋮ Local correctability of expander codes ⋮ Reed-Muller Codes

This page was built for publication: Locally Decodable Codes