Combinatorial construction of locally testable codes

DOI10.1137/080729967MaRDI QIDQ3558012zbMATH OpenOpenAlexFDO

Authors Or Meir

Publication date 29 April 2010

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

Full work available at URL https://semanticscholar.org/paper/29189cbe958616ae20efc09d9fc9f4f27095e548

zbMATH Keywords

probabilistically checkable proofslocally testable codes (LTCs)PCPs of proximity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Other types of codes (94B60)

Recommendations

• Combinatorial construction of locally testable codes (extended abstract)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A combinatorial characterization of smooth LTCs and applications
• Locally testable codes and PCPs of almost-linear length
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cited in

(27)

• Locally Testable Codes Require Redundant Testers
• Towards lower bounds on locally testable codes via density arguments
• Robust locally testable codes and products of codes
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial construction of locally testable codes (extended abstract)
• Short locally testable codes and proofs: a survey in two parts
• On the power of relaxed local decoding algorithms
• The tensor product of two good codes is not necessarily robustly testable
• On the rectangle method in proofs of robustness of tensor products
• A combination of testability and decodability by tensor products
• Relaxed locally correctable codes
• Smooth and strong PCPs
• Local Decoding and Testing for Homomorphisms
• Universal locally testable codes
• Relaxed locally correctable codes
• scientific article; zbMATH DE number 7650135 (Why is no real title available?)
• Short locally testable codes and proofs
• Tensor Products of Weakly Smooth Codes Are Robust
• A combinatorial characterization of smooth LTCs and applications
• On axis-parallel tests for tensor product codes
• Composition of semi-LTCs by two-wise tensor products
• Locally testable codes and PCPs of almost-linear length
• On axis-parallel tests for tensor product codes
• Locally Testable Cyclic Codes
• Local list recovery of high-rate tensor codes and applications
• Dense locally testable codes cannot have constant rate and distance
• Limitation on the Rate of Families of Locally Testable Codes

This page was built for publication: Combinatorial construction of locally testable codes

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