Robust locally testable codes and products of codes

DOI10.1002/rsa.20120zbMath1103.90080OpenAlexW4229760579MaRDI QIDQ5486320

Madhu Sudan, Eli Ben-Sasson

Publication date: 6 September 2006

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20120

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)

Related Items

Spatial Isolation Implies Zero Knowledge Even in a Quantum World ⋮ Single-shot decoding of good quantum LDPC codes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ Unnamed Item ⋮ The tensor product of two good codes is not necessarily robustly testable ⋮ On the rectangle method in proofs of robustness of tensor products ⋮ Composition of semi-LTCs by two-wise tensor products ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Testing low-degree polynomials over prime fields ⋮ Unnamed Item ⋮ Efficient Probabilistically Checkable Debates ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ From Local to Robust Testing via Agreement Testing ⋮ Unnamed Item ⋮ A combination of testability and decodability by tensor products ⋮ Combinatorial PCPs with short proofs

Cites Work

• Unnamed Item
• Some 3CNF properties are hard to test
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Local Expansion of Symmetrical Graphs
• Efficient probabilistically checkable proofs and applications to approximations
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques