Lower bounds for linear locally decodable codes and private information retrieval
DOI10.1007/S00037-006-0216-3zbMATH Open1113.68049OpenAlexW2120217745MaRDI QIDQ862344FDOQ862344
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/
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
Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cited In (24)
- Title not available (Why is that?)
- 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
- High-rate codes with sublinear-time decoding
- On coset leader graphs of structured linear codes
- Smooth and strong PCPs
- 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
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Automata, Languages and Programming
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)
