Composition of semi-LTCs by two-wise tensor products

DOI10.1007/s00037-013-0074-8zbMath1336.94084OpenAlexW2072264369MaRDI QIDQ496304

Michael Viderman, Eli Ben-Sasson

Publication date: 21 September 2015

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-013-0074-8

zbMATH Keywords

tensor productslinear codeslocally testable codesexpander codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Bounds on codes (94B65) Other types of codes (94B60)

Related Items

Unnamed Item, Unnamed Item, Local List Recovery of High-Rate Tensor Codes and Applications, Unnamed Item, From Local to Robust Testing via Agreement Testing, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The tensor product of two good codes is not necessarily robustly testable
• Explicit constructions of graphs without short cycles and low density codes
• Self-testing/correcting with applications to numerical problems
• The communication requirements of efficient allocations and supporting prices
• Local list-decoding and testing of random linear codes from high error
• Short Locally Testable Codes and Proofs
• Expander codes
• A Combination of Testability and Decodability by Tensor Products
• Locally testable codes and PCPs of almost-linear length
• On the Application of LDPC Codes to Arbitrary Discrete-Memoryless Channels
• Combinatorial Construction of Locally Testable Codes
• Low Rate Is Insufficient for Local Testability
• Locally Testable vs. Locally Decodable 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
• High-rate codes with sublinear-time decoding
• Some Applications of Coding Theory in Computational Complexity
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Robust locally testable codes and products of codes
• Some 3CNF Properties Are Hard to Test
• 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