Lower bounds for linear locally decodable codes and private information retrieval

DOI10.1007/S00037-006-0216-3MaRDI QIDQ862344zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Leonard J. Schulman, Luca Trevisan, Howard Karloff

Publication date 24 January 2007

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://authors.library.caltech.edu/27595/

zbMATH Keywords

lower boundslocally decodable codesprivate information retrievalError-correcting codes

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• scientific article; zbMATH DE number 2019623
• Automata, Languages and Programming
• On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

Cited in

(24)

• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Automata, Languages and Programming
• scientific article; zbMATH DE number 2019623 (Why is no real title available?)
• On Locally Decodable Codes, Self-correctable Codes, and t-Private PIR
• On the optimal communication complexity of error-correcting multi-server PIR
• Lower bounds for (batch) PIR with private preprocessing
• Towards lower bounds on locally testable codes via density arguments
• A quadratic lower bound for three-query linear locally decodable codes over any field
• Short locally testable codes and proofs: a survey in two parts
• Lower bounds for 2-query LCCs over large alphabet
• On the power of relaxed local decoding algorithms
• Outlaw distributions and locally decodable codes
• Foundations of homomorphic secret sharing
• On coset leader graphs of structured linear codes
• Smooth and strong PCPs
• High-rate codes with sublinear-time decoding
• Locally decodable codes and private information retrieval schemes.
• On matrix rigidity and locally self-correctable codes
• Short locally testable codes and proofs
• Single-server private information retrieval with sublinear amortized time
• Query-efficient locally decodable codes of subexponential length
• Exponential lower bound for 2-query locally decodable codes via a quantum argument
• Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR

This page was built for publication: Lower bounds for linear locally decodable codes and private information retrieval

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