scientific article; zbMATH DE number 7286915
DOI10.4086/toc.2020.v016a005zbMath1462.68236OpenAlexW3090085778MaRDI QIDQ5140839
Alessandro Chiesa, Peter Manohar, Igor Shinkar
Publication date: 17 December 2020
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2020.v016a005
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
error-correcting codesextremal graph theorylocally testable codestensor product codeslow-degree testing
Linear codes (general theory) (94B05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Randomized algorithms (68W20) Combinatorial codes (94B25)
Cites Work
- Unnamed Item
- Unnamed Item
- The tensor product of two good codes is not necessarily robustly testable
- Composition of semi-LTCs by two-wise tensor products
- Non-deterministic exponential time has two-prover interactive protocols
- Self-testing/correcting with applications to numerical problems
- Improved low-degree testing and its applications
- Linearity testing in characteristic two
- Locally testable codes and PCPs of almost-linear length
- Testing Reed–Muller Codes
- Combinatorial Construction of Locally Testable Codes
- Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
- Robust Local Testability of Tensor Products of LDPC Codes
- Sub-Constant Error Low Degree Test of Almost-Linear Size
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
- Robust Characterizations of Polynomials with Applications to Program Testing
- Short Locally Testable Codes and Proofs: A Survey in Two Parts
- Optimal Testing of Reed-Muller Codes
- A combination of testability and decodability by tensor products
- On codes derivable from the tensor product of check matrices
- Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
- Some optimal inapproximability results
- Robust locally testable codes and products of codes
- On the concrete efficiency of probabilistically-checkable proofs
- Error-locating codes--A new concept in error control
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- On a problem of K. Zarankiewicz
This page was built for publication:
