Lower bounds for adaptive locally decodable codes

DOI10.1002/RSA.20069MaRDI QIDQ5704840zbMATH OpenOpenAlexFDO

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

Publication date 15 November 2005

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20069

zbMATH Keywords

adaptive decoderslocally decodable

Mathematics Subject Classification ID

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

Recommendations

• Private Locally Decodable Codes
• On the efficiency of local decoding procedures for error-correcting codes
• Corruption and Recovery-Efficient Locally Decodable Codes
• scientific article; zbMATH DE number 2019623
• Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Cites work

• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Extractors
• scientific article; zbMATH DE number 2019623 (Why is no real title available?)
• scientific article; zbMATH DE number 1754644 (Why is no real title available?)
• Nearly-linear size holographic proofs
• On the efficiency of local decoding procedures for error-correcting codes
• Pseudorandom generators without the XOR lemma (extended abstract)
• Upper bound on the communication complexity of private information retrieval

Cited in

(6)

• An optimal lower bound for 2-query locally decodable linear codes
• Query-efficient locally decodable codes of subexponential length
• On the power of relaxed local decoding algorithms
• Private Locally Decodable Codes
• Query complexity lower bounds for reconstruction of codes
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704840)