Locally Testable Codes Require Redundant Testers

DOI10.1137/090779875zbMath1209.68265OpenAlexW2055635427MaRDI QIDQ5390594

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

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

linear codeslower boundsproperty testingdual codeslow density parity check codes

Mathematics Subject Classification ID

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

Related Items (8)

Towards lower bounds on locally testable codes via density arguments ⋮ Sparse affine-invariant linear codes are locally testable ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ 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 ⋮ A combinatorial characterization of smooth LTCs and applications

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