On the Power of Relaxed Local Decoding Algorithms
From MaRDI portal
Publication:4989919
DOI10.1137/19M1307834OpenAlexW3156157822MaRDI QIDQ4989919
Publication date: 27 May 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1307834
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (1)
Cites Work
- On the randomness complexity of property testing
- Lower bounds for linear locally decodable codes and private information retrieval
- An adaptivity hierarchy theorem for property testing
- Non-interactive proofs of proximity
- A quadratic lower bound for three-query linear locally decodable codes over any field
- On the efficiency of local decoding procedures for error-correcting codes
- Locally testable codes and PCPs of almost-linear length
- Towards 3-query locally decodable codes of subexponential length
- Combinatorial Construction of Locally Testable Codes
- Two-query PCP with subconstant error
- Locally Testable vs. Locally Decodable Codes
- Outlaw distributions and locally decodable codes
- 3-Query Locally Decodable Codes of Subexponential Length
- Short Locally Testable Codes and Proofs: A Survey in Two Parts
- Relaxed Locally Correctable Codes
- Introduction to Property Testing
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Some Applications of Coding Theory in Computational Complexity
- Tight Lower Bounds for 2-query LCCs over Finite Fields
- Lower bounds for adaptive locally decodable codes
- Automata, Languages and Programming
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Locally Decodable Codes
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the Power of Relaxed Local Decoding Algorithms
