High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity

DOI10.1145/3051093zbMath1426.94160arXiv1504.05653OpenAlexW2617207196MaRDI QIDQ4640284

Or Meir, Noga Ron-Zewi, Swastik Kopparty, Shubhangi Saraf

Publication date: 17 May 2018

Published in: Journal of the ACM, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.05653

zbMATH Keywords

query complexitylocally testable codeslocally decodable codeslocally correctable codessingleton boundasymptotically good codesZyablov bound

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65) Other types of codes (94B60) Decoding (94B35)

Related Items (20)

Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes ⋮ Locality via Partially Lifted Codes ⋮ Unnamed Item ⋮ Erasures versus errors in local decoding and property testing ⋮ Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes ⋮ Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ Relaxed Locally Correctable Codes ⋮ Fast Reed-Solomon Interactive Oracle Proofs of Proximity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Local to Robust Testing via Agreement Testing ⋮ Outlaw distributions and locally decodable codes ⋮ Unnamed Item ⋮ Lifted Multiplicity Codes and the Disjoint Repair Group Property ⋮ List-Decoding with Double Samplers

This page was built for publication: High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity