Lower bounds for adaptive locally decodable codes

DOI10.1002/rsa.20069zbMath1085.94024OpenAlexW2082846050MaRDI QIDQ5704840

Rahul Jain, Telikepalli Kavitha, Amit Deshpande, Jaikumar Radhakrishnan, Satyanarayana V. Lokam

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

zbMATH Keywords

locally decodableadaptive decoders

Mathematics Subject Classification ID

Bounds on codes (94B65) Decoding (94B35)

Related Items (4)

Query-efficient locally decodable codes of subexponential length ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ An optimal lower bound for 2-query locally decodable linear codes

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

This page was built for publication: Lower bounds for adaptive locally decodable codes