Locally Testable Codes Require Redundant Testers

DOI10.1137/090779875MaRDI QIDQ5390594zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Tali Kaufman, Michael Viderman, Venkatesan Guruswami, Madhu Sudan

Publication date 4 April 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

dual codeslinear codeslow density parity check codeslower boundsproperty testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of computing (68Q99)

Recommendations

• Locally testable vs. locally decodable codes
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Universal locally testable codes
• Strong locally testable codes with relaxed local decoders
• Strong locally testable codes with relaxed local decoders
• Locally testable codes with constant rate, distance, and locality
• Tolerant Linearity Testing and Locally Testable Codes
• Bounds on locally testable codes with unique tests
• Combinatorial construction of locally testable codes
• Towards lower bounds on locally testable codes via density arguments

Cited in

(21)

• Sparse affine-invariant linear codes are locally testable
• Bounds on 2-query locally testable codes with affine tests
• A combinatorial characterization of smooth LTCs and applications
• Bounds on locally testable codes with unique tests
• Zero knowledge LTCs and their applications
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Dense locally testable codes cannot have constant rate and distance
• Short locally testable codes and proofs
• Quantum locally testable codes
• Low Rate Is Insufficient for Local Testability
• Locally testable vs. locally decodable codes
• Local testing of lattices
• Universal locally testable codes
• Local testing for membership in lattices
• Limitation on the Rate of Families of Locally Testable Codes
• Short locally testable codes and proofs: a survey in two parts
• Bounds on \(2\)-query codeword testing
• GSF-locality is not sufficient for proximity-oblivious testing
• Towards lower bounds on locally testable codes via density arguments
• Stability of homomorphisms, coverings and cocycles. II: Examples, applications and open problems
• Good locally testable codes

This page was built for publication: Locally Testable Codes Require Redundant Testers

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