arXiv:quant-ph/0403140 · Lecture notes in computer science

Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval

Stephanie Wehner, Ronald de Wolf

Published Jan 1, 2005• 52 citations

Related papers

Lower Bounds for Communication Complexity of Private Information Retrieval

利哉伊東, Toshiya Itoh

On Lower Bounds for the Communication Complexity of Private Information Retrieval

Toshiya Itoh

Doubly efficient private information retrieval: construction, applications and lower bounds

Ethan Mook

Improved upper bounds on information-theoretic private information retrieval

Yuval Ishai

A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval

Iftach Haitner, Jonathan J. Hoch, Gil Segev

Exponential lower bound for 2-query locally decodable codes via a quantum argument

Iordanis Kerenidis, Ronald de Wolf