Query-efficient locally decodable codes of subexponential length
From MaRDI portal
Publication:1947042
DOI10.1007/s00037-011-0017-1zbMath1311.94123arXiv1008.1617OpenAlexW2154522281MaRDI QIDQ1947042
Tao Feng, Yeow Meng Chee, Liang Feng Zhang, Huaxiong Wang, San Ling
Publication date: 11 April 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1008.1617
Related Items
On the optimal communication complexity of error-correcting multi-server PIR ⋮ Locally Decodable Codes: A Brief Survey ⋮ Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ High-rate codes with sublinear-time decoding
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for linear locally decodable codes and private information retrieval
- An optimal lower bound for 2-query locally decodable linear codes
- Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
- General constructions for information-theoretic private information retrieval
- Private information retrieval
- On the efficiency of local decoding procedures for error-correcting codes
- A Geometric Approach to Information-Theoretic Private Information Retrieval
- Towards 3-query locally decodable codes of subexponential length
- Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
- Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers
- Upper bound on the communication complexity of private information retrieval
- 3-query locally decodable codes of subexponential length
- Some Applications of Coding Theory in Computational Complexity
- Lower bounds for adaptive locally decodable codes
- Automata, Languages and Programming
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
