Robust locally testable codes and products of codes

DOI10.1002/RSA.20120zbMATH Open1103.90080OpenAlexW4229760579MaRDI QIDQ5486320FDOQ5486320

Authors: Eli Ben-Sasson, Madhu Sudan 

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

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Robust Local Testability of Tensor Products of LDPC Codes
• Strong locally testable codes with relaxed local decoders
• Strong locally testable codes with relaxed local decoders
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Combinatorial construction of locally testable codes
• Combinatorial construction of locally testable codes (extended abstract)
• Locally testable codes with constant rate, distance, and locality
• Locally testable vs. locally decodable codes
• Locally testable codes and Cayley graphs

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)

Cites Work

• Title not available (Why is that?)
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Efficient probabilistically checkable proofs and applications to approximations
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Local Expansion of Symmetrical Graphs
• Some 3CNF properties are hard to test

Cited In (26)

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

This page was built for publication: Robust locally testable codes and products of codes

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