Locally Testable Codes Require Redundant Testers
From MaRDI portal
Publication:5390594
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
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