On axis-parallel tests for tensor product codes

DOI10.4086/TOC.2020.V016A005MaRDI QIDQ5140839zbMATH OpenOpenAlexFDO

Authors Alessandro Chiesa, Peter Manohar, Igor Shinkar

Publication date 17 December 2020

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2020.v016a005

zbMATH Keywords

error-correcting codesextremal graph theorylocally testable codeslow-degree testingtensor product codes

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Randomized algorithms (68W20) Linear codes (general theory) (94B05) Combinatorial codes (94B25)

Recommendations

• On axis-parallel tests for tensor product codes
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Robust Local Testability of Tensor Products of LDPC Codes
• Robust locally testable codes and products of codes
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cites work

• A combination of testability and decodability by tensor products
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Combinatorial construction of locally testable codes
• Composition of semi-LTCs by two-wise tensor products
• Error-locating codes--A new concept in error control
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Improved low-degree testing and its applications
• Linearity testing in characteristic two
• Locally testable codes and PCPs of almost-linear length
• Non-deterministic exponential time has two-prover interactive protocols
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
• On a problem of K. Zarankiewicz
• On codes derivable from the tensor product of check matrices
• On the concrete efficiency of probabilistically-checkable proofs
• Optimal testing of Reed-Muller codes
• Probabilistic checking of proofs
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust Local Testability of Tensor Products of LDPC Codes
• Robust locally testable codes and products of codes
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Self-testing/correcting with applications to numerical problems
• Short locally testable codes and proofs: a survey in two parts
• Short PCPs with Polylog Query Complexity
• Some optimal inapproximability results
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Tensor products of weakly smooth codes are robust
• Testing Reed–Muller Codes
• The tensor product of two good codes is not necessarily robustly testable

Cited in

(1)

• On axis-parallel tests for tensor product codes

This page was built for publication: On axis-parallel tests for tensor product codes

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