Robust locally testable codes and products of codes

DOI10.1002/RSA.20120MaRDI QIDQ5486320zbMATH OpenOpenAlexFDO

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

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

• 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

Cites work

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Efficient probabilistically checkable proofs and applications to approximations
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Local Expansion of Symmetrical Graphs
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Some 3CNF properties are hard to test

Cited in

(31)

• Combinatorial PCPs with short proofs
• 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)
• A combinatorial characterization of smooth LTCs and applications
• Testing low-degree polynomials over prime fields
• Efficient Probabilistically Checkable Debates
• A combination of testability and decodability by tensor products
• Robust Local Testability of Tensor Products of LDPC Codes
• Composition of Semi-LTCs by Two-Wise 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
• Limitation on the Rate of Families of Locally Testable Codes
• Composition of semi-LTCs by two-wise tensor products
• On axis-parallel tests for tensor product codes
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Spatial Isolation Implies Zero Knowledge Even in a Quantum World
• From Local to Robust Testing via Agreement Testing
• From local to robust testing via agreement testing
• Local list recovery of high-rate tensor codes and applications
• On axis-parallel tests for tensor product codes
• A combination of testability and decodability by tensor products
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 7650135 (Why is no real title available?)
• Single-shot decoding of good quantum LDPC codes
• Zero-knowledge IOPs approaching witness length
• Untangling the security of Kilian's protocol: upper and lower bounds
• Proving as fast as computing: succinct arguments with constant prover overhead
• Local proofs approaching the witness length
• Good locally testable codes
• Testing tensor products of algebraic 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)