High-rate codes with sublinear-time decoding

DOI10.1145/1993636.1993660zbMath1288.94112OpenAlexW2021999231MaRDI QIDQ5419086

Sergey Yekhanin, Swastik Kopparty, Shubhangi Saraf

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1993636.1993660

zbMATH Keywords

polynomialsderivativeserror-correcting codeslocally decodable codessublinear-time algorithmsmultiplicity codes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Decoding (94B35)

Related Items (12)

Locality via Partially Lifted Codes ⋮ Fast systematic encoding of multiplicity codes ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ Locally Decodable Codes: A Brief Survey ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Locally Decodable Codes ⋮ Optimal Rate List Decoding via Derivative Codes ⋮ Public Key Locally Decodable Codes with Short Keys ⋮ A geometric approach to homomorphic secret sharing ⋮ Local correctability of expander codes

This page was built for publication: High-rate codes with sublinear-time decoding