A quadratic lower bound for three-query linear locally decodable codes over any field
From MaRDI portal
Publication:2637284
DOI10.1007/s11390-012-1254-8zbMath1280.94123OpenAlexW2144581009MaRDI QIDQ2637284
Publication date: 11 February 2014
Published in: Journal of Computer Science and Technology (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11390-012-1254-8
Linear codes (general theory) (94B05) Bounds on codes (94B65) Decoding (94B35) Synchronization error-correcting codes (94B50)
Related Items
On coset leader graphs of structured linear codes, On the Power of Relaxed Local Decoding Algorithms, Outlaw distributions and locally decodable codes
Cites Work
- Unnamed Item
- Unnamed Item
- Lower bounds for linear locally decodable codes and private information retrieval
- Locally decodable codes and private information retrieval schemes.
- Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
- Matching Vector Codes
- Expander codes
- On the efficiency of local decoding procedures for error-correcting codes
- Corruption and Recovery-Efficient Locally Decodable Codes
- Towards 3-query locally decodable codes of subexponential length
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
- 3-query locally decodable codes of subexponential length
- Some Applications of Coding Theory in Computational Complexity
- Compressed sensing
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
