|
| related topics |
| {algorithm, log, probability} |
| {key, protocol, security} |
| {error, code, errors} |
| {let, theorem, proof} |
| {states, state, optimal} |
|
Improved Lower Bounds for Locally Decodable Codes and Private
Information Retrieval
Stephanie Wehner, Ronald de Wolf
abstract: 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 l-bit
alphabet, where the decoder only uses b bits of each queried position of the
codeword, needs code length m = exp(Omega(n/(2^b Sum_{i=0}^b {l choose i})))
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 l-bit answers, unknown to
the servers, satisfies t = Omega(n/(2^b Sum_{i=0}^b {l choose i})). This
implies that several known PIR schemes are close to optimal. Our results
generalize those of Goldreich et al. who proved roughly the same bounds for
linear LDCs and PIRs. Like earlier work by Kerenidis and de Wolf, our classical
lower 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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0403140
- categories:
- quant-ph cs.CC cs.CR
- comments:
- 12 pages LaTeX, To appear in ICALP '05
- doi:
- 10.1007/11523468_115
- arxiv_id:
- quant-ph/0403140
- journal_ref:
- Proc. of 32nd ICALP, 2005, LNCS 3580, pages 1424-1436.
- created:
- 2004-03-19
- updated:
- 2005-05-19
Full article ▸
|
|
| related documents |
| 0410042v1 |
| 0304131v1 |
| 9907020v2 |
| 0010034v1 |
| 0607148v3 |
| 0207131v1 |
| 9903071v1 |
| 0511272v1 |
| 0505007v3 |
| 0201152v1 |
| 9905026v1 |
| 9802040v2 |
| 0302022v1 |
| 0504067v3 |
| 9706003v4 |
| 0206089v2 |
| 0210077v1 |
| 0303175v1 |
| 0612089v3 |
| 0408150v2 |
| 0008059v3 |
| 0609220v1 |
| 0610235v2 |
| 0609166v1 |
| 0510185v1 |
|