Strong locally testable codes with relaxed local decoders

DOI10.1145/3319907MaRDI QIDQ5205813zbMATH OpenOpenAlexWikidataFDO

Authors Oded Goldreich, Tom Gur, Ilan Komargodski

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2015/5050/

zbMATH Keywords

error-correcting codeslocal decodabilitylocal testability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Other types of codes (94B60)

Recommendations

• Strong locally testable codes with relaxed local decoders
• Relaxed locally correctable codes
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Relaxed locally correctable codes
• On the power of relaxed local decoding algorithms

Cited in

(14)

• Smooth and strong PCPs
• Bounds on locally testable codes with unique tests
• Zero knowledge LTCs and their applications
• Dense locally testable codes cannot have constant rate and distance
• Locally testable vs. locally decodable codes
• Local Decoding and Testing for Homomorphisms
• Strong locally testable codes with relaxed local decoders
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Every Set in P Is Strongly Testable Under a Suitable Encoding
• Locally Testable Codes Require Redundant Testers
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Robust locally testable codes and products of codes
• Relaxed locally correctable codes
• On the relaxed LDC of BGHSV: a survey that corrects the record

This page was built for publication: Strong locally testable codes with relaxed local decoders

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