Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval
verfasst von : Stephanie Wehner, Ronald de Wolf
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We prove new lower bounds for
locally decodable codes
and
private information retrieval
. We show that a 2-query LDC encoding
n
-bit strings over an ℓ-bit alphabet, where the decoder only uses
b
bits of each queried position, needs code length
$m=exp\left(\Omega\left(\frac{n}{2^{b}{\sum_{i=0}^{b}}(^{l}_{i})}\right)\right)$
Similarly, a 2-server PIR scheme with an
n
-bit database and
t
-bit queries, where the user only needs
b
bits from each of the two ℓ-bit answers, unknown to the servers, satisfies
$t=\Omega \left(\frac{n}{2^{b}\sum_{i=0}^{b}(^{l}_{i})}\right)$
This implies that several known PIR schemes are close to optimal. Our results generalize those of Goldreich et al. [8], who proved roughly the same bounds for
linear
LDCs and PIRs. Like earlier work by Kerenidis and de Wolf [12], our classical bounds are proved using quantum computational techniques. In particular, we give a tight analysis of how well a 2-input function can be computed from a quantum superposition of both inputs.