Erasures versus errors in local decoding and property testing
From MaRDI portal
Publication:6074671
DOI10.1002/rsa.21031zbMath1522.68750OpenAlexW3178276004MaRDI QIDQ6074671
Noga Ron-Zewi, Nithin Varma, Sofya Raskhodnikova
Publication date: 12 October 2023
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.21031
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial PCPs with short proofs
- Combinatorial PCPs with efficient verifiers
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Query complexity in errorless hardness amplification
- Bounds for codes in the case of list decoding of finite volume
- Highly resilient correctors for polynomials
- Self-testing/correcting with applications to numerical problems
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Fast approximate probabilistically checkable proofs
- Tolerant property testing and distance approximation
- Learning Polynomials with Queries: The Highly Noisy Case
- Nearly-linear size holographic proofs
- Local List-Decoding and Testing of Random Linear Codes from High Error
- Some remarks on multiplicity codes
- List-Decoding Algorithms for Lifted Codes
- A Brief Introduction to Property Testing
- Introduction to Testing Graph Properties
- Matching Vector Codes
- Proof verification and the hardness of approximation problems
- Property testing and its connection to learning and approximation
- Private information retrieval
- On the efficiency of local decoding procedures for error-correcting codes
- The Complexity of Local List Decoding
- Towards 3-query locally decodable codes of subexponential length
- List decoding from erasures: bounds and code constructions
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- Probabilistic checking of proofs
- Learning Decision Trees Using the Fourier Spectrum
- Erasure-Resilient Property Testing
- High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
- Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound
- Robust Characterizations of Polynomials with Applications to Program Testing
- 3-Query Locally Decodable Codes of Subexponential Length
- Local List Recovery of High-Rate Tensor Codes and Applications
- lgorithmic and Analysis Techniques in Property Testing
- A Lower Bound on List Size for List Decoding
- Introduction to Property Testing
- Some Applications of Coding Theory in Computational Complexity
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- 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
- Pseudorandom generators without the XOR lemma
This page was built for publication: Erasures versus errors in local decoding and property testing
