The characterization of MDS-PIR capacity-achieving codes

Let C\mathcal{C} be an [n,k][n,k] code, and let dsCd_s^{\mathcal{C}} denote the quantity appearing in the necessary condition

dsCnks,s{1,,k}.d_s^{\mathcal{C}}\geq\frac{n}{k}s,\quad\forall\,s\in\{1,\ldots,k\}.

An MDS-PIR capacity-achieving matrix Λκ,ν(C)\bm{\Lambda}_{\kappa,\nu}(\mathcal{C}) has parameters satisfying κν=kn\frac{\kappa}{\nu}=\frac{k}{n}. MDS-PIR characterization conjecture. Such a matrix exists if and only if

dsCnks,s{1,,k}.d_s^{\mathcal{C}}\geq\frac{n}{k}s,\quad\forall\,s\in\{1,\ldots,k\}.

The condition is necessary for the existence of an MDS-PIR capacity-achieving matrix. Exhaustive searches for parameters up to length 1111, with the stated exceptions [n,k]=[10,5][n,k]=[10,5] and [n,k]=[11,4k7][n,k]=[11,4\leq k\leq 7], found a matrix whenever the condition held, but sufficiency remains open in general.

Sources & referencesView supporting material

Primary source

Hsuan-Yin Lin, Siddhartha Kumar, Eirik Rosnes and Alexandre Graell i Amat, “An MDS-PIR Capacity-Achieving Protocol for Distributed Storage Using Non-MDS Linear Codes”, arXiv:1801.04923 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.