Lower bounds for linear locally decodable codes and private information retrieval

DOI10.1007/s00037-006-0216-3zbMath1113.68049OpenAlexW2120217745MaRDI QIDQ862344

Leonard J. Schulman, Oded Goldreich, Luca Trevisan, Howard J. 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 boundsError-correcting codeslocally decodable codesprivate information retrieval

Mathematics Subject Classification ID

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

Related Items (18)

A quadratic lower bound for three-query linear locally decodable codes over any field ⋮ Single-server private information retrieval with sublinear amortized time ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ Unnamed Item ⋮ On the optimal communication complexity of error-correcting multi-server PIR ⋮ Query-efficient locally decodable codes of subexponential length ⋮ On matrix rigidity and locally self-correctable codes ⋮ Foundations of Homomorphic Secret Sharing ⋮ On coset leader graphs of structured linear codes ⋮ Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin. ⋮ Towards lower bounds on locally testable codes via density arguments ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Smooth and strong PCPs ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ Short Locally Testable Codes and Proofs ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Outlaw distributions and locally decodable codes ⋮ High-rate codes with sublinear-time decoding

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