25 problems

Let $M$ files be stored across $N$ servers, with each file stored independently using the same $(N,K)$-MDS code. A user wants to retrieve one file without revealing its index to an…

Let an $[n,k]$ MDS storage code store a database accessed by a Symmetric Private Information Retrieval scheme, with $t$-colluding servers, $b$ Byzantine servers, and $r$ unresponsi…

Let U-B-XS-MDS-TPIR denote the considered private information retrieval problem with its corresponding parameters, and let $C_\infty$ be its asymptotic capacity for a large number…

Let $\mathcal{C}$ be an $[n,k]$ code, and let $d_s^{\mathcal{C}}$ denote the quantity appearing in the necessary condition … An MDS-PIR capacity-achieving matrix…

Let $ASP(k,t,q)$ and $ASB(k,t,q)$ denote the minimum lengths of, respectively, all-symbol PIR and all-symbol batch codes with parameters $k,t,q$. For all $k,q$ and $t_1,t_2\geq 1$,…

Recursive-framework conjecture. This recursive framework can be extended to construct efficient PIR schemes for certain broader classes of graphs.

Sadeh's conjecture. The upper bound $\frac{2}{N+1}$ might be tight for $K_N$, and this rate could potentially be achieved by a more sophisticated PIR scheme.

The multi-file setting involves servers storing more than two files, while a two-file-per-server algorithm retrieves files by reducing the problem to instances with two files at ea…

PPIR-MSI rate-bound conjecture. The PPIR-MSI rate $R_\mathrm{PPIR-MSI}$ must satisfy

Identifiable-side-information rate conjecture. The rate $R_\mathrm{PPIR-SI}=\frac{1}{\Gamma-\eta+1}$ is achievable.

General-capacity conjecture. For every $K,D,M$, the general capacity of IPIR does not exceed the linear capacity, and both are given by

Linear-capacity conjecture. The linear capacity of IPIR is

Heidarzadeh et al.'s PIR-PCSI-II capacity conjecture. The capacity in this range should be

Multi-server PIR-RSSI capacity conjecture. The capacity of multi-server PIR-RSSI is given by

Let U-B-MDS-MB-XTSPIR denote the multi-user blind symmetric private information retrieval problem with coded servers, including the parameters governing the number of servers, codi…

Capacity equality conjecture. The capacities of the JPC-SI and JPC-CSI settings are the same for both linear and non-linear protocols.

Finite-file PIR rate conjecture. Any such PIR scheme has rate at most

Asymptotic PIR capacity conjecture. The asymptotic capacity as the number of files $m$ tends to infinity is

Private-side-information conjecture. The capacity of any PIR problem with private side information of size $M$ is the same as the capacity of the same problem without side informat…

For an $(N,K,T,M)$ private information retrieval scheme, let $R$ denote its rate, and let the rate in equation be the rate under consideration. The optimal-rate conjecture. The rat…

Let $C$ be the storage code and $D$ the query code in a symmetric PIR scheme, and let $\dim C\star D$ denote the dimension of their star-product code. The scheme uses shared random…

Let $\mathrm{RM}_2(m,1)$ denote the binary Reed–Muller code of order $1$, and let $\mathrm{IC}_2(\mathrm{RM}_2(m,1))$ denote its incidence code. A PIR protocol is $t$-private if it…

Consider an $(N,M)$-MDS-coded database with $K\geq 2$ files and $T$-private symmetric private information retrieval, where any $T$ nodes may collude. For queries $Q_i^{[k]}$ and an…

Let an $(N,M)$-MDS-coded database store $K\geq 2$ files at $N$ nodes, where any $T$ nodes may collude. Let $T$-private symmetric private information retrieval (MDS-TSPIR) require u…

Let $s>2$, and consider the PIR array codes produced by the B-E Construction. B-E optimality conjecture. These PIR array codes have optimal rate. The preceding discussion is based…