Locally testable vs. locally decodable codes

DOI10.1007/978-3-642-15369-3_50MaRDI QIDQ3588443zbMATH OpenOpenAlexFDO

Authors Tali Kaufman, Michael Viderman

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15369-3_50

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35) Error probability in coding theory (94B70)

Recommendations

• Locally Testable Codes Require Redundant Testers
• Strong locally testable codes with relaxed local decoders
• Strong locally testable codes with relaxed local decoders
• Dense locally testable codes cannot have constant rate and distance
• Combinatorial construction of locally testable codes (extended abstract)

Cited in

(16)

• On coset leader graphs of structured linear codes
• Locally testable codes and PCPs of almost-linear length
• Locally Testable Cyclic Codes
• Local Decoding and Testing for Homomorphisms
• Locally Testable and Locally Correctable Codes Approaching the Gilbert-Varshamov Bound
• Universal locally testable codes
• Limitation on the Rate of Families of Locally Testable Codes
• Composition of semi-LTCs by two-wise tensor products
• On the power of relaxed local decoding algorithms
• A combination of testability and decodability by tensor products
• Locally Testable Codes Require Redundant Testers
• Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
• Robust locally testable codes and products of codes
• Locally Decodable Codes
• Locally testable codes with constant rate, distance, and locality
• Towards lower bounds on locally testable codes via density arguments

This page was built for publication: Locally testable vs. locally decodable codes

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