English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We prove new lower bounds for locally decodable codes and private informationretrieval. We show that a 2-query LDC encoding n-bit strings over an l-bitalphabet, where the decoder only uses b bits of each queried position of thecodeword, 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 tothe servers, satisfies t = Omega(n/(2^b Sum_{i=0}^b {l choose i})). Thisimplies that several known PIR schemes are close to optimal. Our resultsgeneralize those of Goldreich et al. who proved roughly the same bounds forlinear LDCs and PIRs. Like earlier work by Kerenidis and de Wolf, our classicallower 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 aquantum superposition of both inputs.Comment: 12 pages LaTeX, To appear in ICALP '0

Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval