High-rate codes with sublinear-time decoding

DOI10.1145/1993636.1993660MaRDI QIDQ5419086zbMATH OpenOpenAlexFDO

Authors Swastik Kopparty, Sergey Yekhanin, 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

derivativeserror-correcting codeslocally decodable codesmultiplicity codespolynomialssublinear-time algorithms

Mathematics Subject Classification ID

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

Recommendations

• High-rate codes with sublinear-time decoding
• List-decoding multiplicity codes
• On the efficiency of local decoding procedures for error-correcting codes
• Some remarks on multiplicity codes

Cited in

(20)

• A geometric approach to homomorphic secret sharing
• Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes
• Local correctability of expander codes
• Fast systematic encoding of multiplicity codes
• Local list-decoding and testing of random linear codes from high error
• Local list-decoding and testing of random linear codes from high error
• List-decoding multiplicity codes
• Locally decodable codes: a brief survey
• Optimal Rate List Decoding via Derivative Codes
• Public key locally decodable codes with short keys
• Matching vector codes
• On the efficiency of local decoding procedures for error-correcting codes
• Some remarks on multiplicity codes
• Codes with local decoding procedures
• Composition of semi-LTCs by two-wise tensor products
• Locality via partially lifted codes
• High-rate codes with sublinear-time decoding
• Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes
• Locally Decodable Codes
• Towards lower bounds on locally testable codes via density arguments

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419086)