Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound

DOI10.1137/1.9781611974782.135MaRDI QIDQ4575883zbMATH OpenOpenAlexFDO

Authors

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.135

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial codes (94B25) Bounds on codes (94B65)

Recommendations

• Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound
• Towards lower bounds on locally testable codes via density arguments
• Locally testable codes with constant rate, distance, and locality
• Locally testable vs. locally decodable codes
• Bounds on locally testable codes with unique tests
• Locally testable codes and PCPs of almost-linear length
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Combinatorial construction of locally testable codes (extended abstract)

Cited in

(8)

• Outlaw distributions and locally decodable codes
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Erasures vs. errors in local decoding and property testing
• Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates
• Fast Reed-Solomon interactive oracle proofs of proximity
• Limitation on the Rate of Families of Locally Testable Codes
• Locally testable codes with constant rate, distance, and locality
• Locally testable codes and PCPs of almost-linear length

This page was built for publication: Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound

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