MDS conjecture for general codes

Let G=([n],E)G=([n],E) be a kk-uniform hypergraph, and let q(G)q(G) be the smallest alphabet size for which there are encoding and decoding functions recovering every message from the symbols on every edge of GG. For the complete nn-vertex kk-uniform hypergraph κn,k\kappa_{n,k}, q(κn,k)q(\kappa_{n,k}) is the minimum alphabet size of a general (n,k)(n,k) MDS code. For integers k<q6k<q\neq 6, let n(q,k)n(q,k) be the largest integer nn such that q(κn,k)qq(\kappa_{n,k})\leq q. MDS conjecture for general codes.

n(q,k){q+2if 4q and k{3,q1},\q+1otherwise.n(q,k)\leq\begin{cases}q+2 & \text{if }4\mid q\text{ and }k\in\{3,q-1\},\q+1 & \text{otherwise.}\end{cases}

This is the classical upper bound on the length of general MDS codes over an alphabet of size qq. The supplied status evidence says that the linear version over prime fields has been proved, but it does not establish resolution of this general-code statement; its database status is therefore left open.

Sources & referencesView supporting material

Primary source

Mira Gonen, Ishay Haviv, Michael Langberg and Alex Sprintson, “Minimizing the alphabet size of erasure codes with restricted decoding sets”, arXiv:2005.06947 (2020).

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.