On the power of relaxed local decoding algorithms
From MaRDI portal
Recommendations
- On the power of relaxed local decoding algorithms
- Relaxed locally correctable codes
- Relaxed locally correctable codes
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
Cites work
- 3-query locally decodable codes of subexponential length
- A quadratic lower bound for three-query linear locally decodable codes over any field
- An adaptivity hierarchy theorem for property testing
- Automata, Languages and Programming
- Combinatorial construction of locally testable codes
- Composition of low-error 2-query PCPs using decodable PCPs
- Efficient and error-correcting data structures for membership and polynomial evaluation
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- scientific article; zbMATH DE number 2019623 (Why is no real title available?)
- Introduction to Property Testing
- Locally decodable codes
- Locally testable codes and PCPs of almost-linear length
- Locally testable vs. locally decodable codes
- Lower bounds for adaptive locally decodable codes
- Lower bounds for linear locally decodable codes and private information retrieval
- Non-interactive proofs of proximity
- On the efficiency of local decoding procedures for error-correcting codes
- On the randomness complexity of property testing
- Outlaw distributions and locally decodable codes
- Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
- Relaxed locally correctable codes
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- Short locally testable codes and proofs: a survey in two parts
- Some Applications of Coding Theory in Computational Complexity
- Strong locally testable codes with relaxed local decoders
- Superquadratic lower bound for 3-query locally correctable codes over the reals
- Tight Lower Bounds for 2-query LCCs over Finite Fields
- Towards 3-query locally decodable codes of subexponential length
- Two-query PCP with subconstant error
- Universal locally testable codes
Cited in
(14)- Locally decodable codes: a brief survey
- The Complexity of Local List Decoding
- FGLM-Like Decoding: from Fitzpatrick’s Approach to Recent Developments
- Relaxed locally correctable codes
- scientific article; zbMATH DE number 7376033 (Why is no real title available?)
- On the power of relaxed local decoding algorithms
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- Query complexity lower bounds for reconstruction of codes
- Relaxed locally correctable codes
- Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Asymptotically-good RLCCs with \((\log n)^{2+o(1)}\) queries
- On the relaxed LDC of BGHSV: a survey that corrects the record
- On the lower bound on the length of relaxed locally decodable codes
This page was built for publication: On the power of relaxed local decoding algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989919)
