On the rectangle method in proofs of robustness of tensor products

DOI10.1016/j.ipl.2011.11.007zbMath1242.94046MaRDI QIDQ437691

Or Meir

Publication date: 18 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.11.007

zbMATH Keywords

robust; robustness; tensor product; theory of computation; locally testable codes; product code; LTC

Mathematics Subject Classification ID

94B60: Other types of codes

Related Items

Local List Recovery of High-Rate Tensor Codes and Applications, A combination of testability and decodability by tensor products, The tensor product of two good codes is not necessarily robustly testable

Cites Work

• Unnamed Item
• The tensor product of two good codes is not necessarily robustly testable
• Nearly-linear size holographic proofs
• Short Locally Testable Codes and Proofs
• A Combination of Testability and Decodability by Tensor Products
• Locally testable codes and PCPs of almost-linear length
• Combinatorial Construction of Locally Testable Codes
• Robust Local Testability of Tensor Products of LDPC Codes
• Short PCPs with Polylog Query Complexity
• Composition of Semi-LTCs by Two-Wise Tensor Products
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Robust locally testable codes and products of codes
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• The PCP theorem by gap amplification