Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On the Storage Cost of Private Information Retrieval   We consider the fundamental tradeoff between the storage cost and the
download cost in private information retrieval systems, without any explicit
structural restrictions on the storage codes, such as maximum distance
separable codes or uncoded storage. Two novel outer bounds are provided, which
have the following implications. When the messages are stored without any
redundancy across the databases, the optimal PIR strategy is to download all
the messages; on the other hand, for PIR capacity-achieving codes, each
database can reduce the storage cost, from storing all the messages, by no more
than one message on average. We then focus on the two-message two-database
case, and show that a stronger outer bound can be derived through a novel
pseudo-message technique. This stronger outer bound suggests that a precise
characterization of the storage-download tradeoff may require non-Shannon type
inequalities, or at least more sophisticated bounding techniques.

32
The categories of this paper are: atom-ph
18
The categories of this paper are: econ
31
The categories of this paper are: ao-sci
27
The categories of this paper are: comp-gas
15
The categories of this paper are: nucl-ex
24
The categories of this paper are: dg-ga
12
The categories of this paper are: nucl-th
16
The categories of this paper are: stat
10
The categories of this paper are: q-bio
36
The categories of this paper are: cmp-lg
21
The categories of this paper are: adap-org
25
The categories of this paper are: patt-sol
19
The categories of this paper are: eess
33
The categories of this paper are: plasm-ph
23
The categories of this paper are: solv-int
26
The categories of this paper are: bayes-an