Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Capacity of Private Information Retrieval from Uncoded Storage
  Constrained Databases   Private information retrieval (PIR) allows a user to retrieve a desired
message from a set of databases without revealing the identity of the desired
message. The replicated databases scenario was considered by Sun and Jafar,
2016, where $N$ databases can store the same $K$ messages completely. A PIR
scheme was developed to achieve the optimal download cost given by $\left(1+
\frac{1}{N}+ \frac{1}{N^{2}}+ \cdots + \frac{1}{N^{K-1}}\right)$. In this work,
we consider the problem of PIR from storage constrained databases. Each
database has a storage capacity of $\mu KL$ bits, where $L$ is the size of each
message in bits, and $\mu \in [1/N, 1]$ is the normalized storage. On one
extreme, $\mu=1$ is the replicated databases case. On the other hand, when
$\mu= 1/N$, then in order to retrieve a message privately, the user has to
download all the messages from the databases achieving a download cost of
$1/K$. We aim to characterize the optimal download cost versus storage
trade-off for any storage capacity in the range $\mu \in [1/N, 1]$. For any
$(N,K)$, we show that the optimal trade-off between storage, $\mu$, and the
download cost, $D(\mu)$, is given by the lower convex hull of the $N$ pairs
$\left(\mu= \frac{t}{N},D(\mu) = \left(1+ \frac{1}{t}+ \frac{1}{t^{2}}+ \cdots
+ \frac{1}{t^{K-1}}\right)\right)$ for $t=1,2,\ldots, N$. To prove this result,
we first present the storage constrained PIR scheme for any $(N,K)$. We next
obtain a general lower bound on the download cost for PIR, which is valid for
the following storage scenarios: replicated or storage constrained, coded or
uncoded, and fixed or optimized. We then specialize this bound using the
uncoded storage assumption to obtain lower bounds matching the achievable
download cost of the storage constrained PIR scheme for any value of the
available storage.

9
The categories of this paper are: nlin
28
The categories of this paper are: alg-geom
18
The categories of this paper are: econ
0
The categories of this paper are: hep-ph
6
The categories of this paper are: astro-ph
14
The categories of this paper are: math-ph
7
The categories of this paper are: hep-th
22
The categories of this paper are: chao-dyn
26
The categories of this paper are: bayes-an
31
The categories of this paper are: ao-sci
34
The categories of this paper are: chem-ph
35
The categories of this paper are: mtrl-th
13
The categories of this paper are: quant-ph
8
The categories of this paper are: hep-ex
4
The categories of this paper are: cond-mat
3
The categories of this paper are: physics