Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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• 69 citations
arXivHTMLPDF
DOI
10.1007/11523468_115

Related papers

Lower Bounds for Communication Complexity of Private Information Retrieval

利哉 伊東, Toshiya Itoh

•Jan 1, 2000•0 citations

On Lower Bounds for the Communication Complexity of Private Information Retrieval

Toshiya Itoh

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2001•16 citations

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

Ethan Mook

•Jan 1, 2026•0 citations

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

Iftach Haitner, Jonathan J. Hoch, Gil Segev

Springer eBooks•Feb 25, 2008•12 citations

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

Iordanis Kerenidis, Ronald de Wolf

arXiv:quant-ph/0208062•Journal of Computer and System Sciences•Aug 4, 2004•141 citations

Upper and Lower Bounds on the Capacity of Private Information Retrieval Allowing Information Leakage from Queries with Different Limits for Each Database

Naoto Toyoda, Tetsunao Matsuta, Uyematsu Tomohiko

IEICE Technical Report; IEICE Tech. Rep.•Feb 25, 2021•0 citations