A combination of testability and decodability by tensor products
From MaRDI portal
Publication:5252263
DOI10.1002/rsa.20498zbMath1316.94112OpenAlexW2125293366MaRDI QIDQ5252263
Publication date: 29 May 2015
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20498
Related Items
Faster sounder succinct arguments and \textsf{IOP}s ⋮ Unnamed Item ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ 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
- The tensor product of two good codes is not necessarily robustly testable
- On the rectangle method in proofs of robustness of tensor products
- Non-deterministic exponential time has two-prover interactive protocols
- Self-testing/correcting with applications to numerical problems
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Improved low-degree testing and its applications
- Local list-decoding and testing of random linear codes from high error
- List Decoding Tensor Products and Interleaved Codes
- Proof verification and the hardness of approximation problems
- Private information retrieval
- Simple extractors for all min-entropies and a new pseudorandom generator
- Locally testable codes and PCPs of almost-linear length
- Towards 3-query locally decodable codes of subexponential length
- Testing Reed–Muller Codes
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- Improved Nearly-MDS Expander Codes
- Combinatorial Construction of Locally Testable Codes
- Two-query PCP with subconstant error
- Low Rate Is Insufficient for Local Testability
- Locally Testable vs. Locally Decodable Codes
- Composition of Semi-LTCs by Two-Wise Tensor Products
- Probabilistic checking of proofs
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Algebraic methods for interactive proof systems
- IP = PSPACE
- IP = SPACE
- 3-query locally decodable codes of subexponential length
- 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
- Introduction to Coding Theory
- The PCP theorem by gap amplification
- Pseudorandom generators without the XOR lemma
