Low Rate Is Insufficient for Local Testability

DOI10.1007/978-3-642-15369-3_32MaRDI QIDQ3588425zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, 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_32

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Recommendations

• Testing alone is insufficient
• Locally Testable Codes Require Redundant Testers
• Local Testing of Message Sequence Charts Is Difficult
• Low-degree tests at large distances
• scientific article; zbMATH DE number 1003235
• Local testing of lattices
• 2-transitivity is insufficient for local testability
• Efficient testing without efficient regularity
• Improved low-degree testing and its applications
• Dense locally testable codes cannot have constant rate and distance

Cited in

(6)

• Succinct representation of codes with applications to testing
• Limitation on the Rate of Families of Locally Testable Codes
• Some recent results on local testing of sparse linear codes
• Composition of semi-LTCs by two-wise tensor products
• A combination of testability and decodability by tensor products
• Towards lower bounds on locally testable codes via density arguments

This page was built for publication: Low Rate Is Insufficient for Local Testability

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