Lower bounds for adaptive locally decodable codes
From MaRDI portal
Publication:5704840
DOI10.1002/rsa.20069zbMath1085.94024MaRDI QIDQ5704840
Jaikumar Radhakrishnan, Telikepalli Kavitha, Rahul Jain, Satyanarayana V. Lokam, Amit Deshpande
Publication date: 15 November 2005
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20069
Related Items
Exponential lower bound for 2-query locally decodable codes via a quantum argument, An optimal lower bound for 2-query locally decodable linear codes, Query-efficient locally decodable codes of subexponential length
Cites Work
- Unnamed Item
- Unnamed Item
- Nearly-linear size holographic proofs
- Pseudorandom generators without the XOR Lemma (extended abstract)
- On the efficiency of local decoding procedures for error-correcting codes
- Extractors
- Upper bound on the communication complexity of private information retrieval
- Exponential lower bound for 2-query locally decodable codes via a quantum argument