32 problems

Let $q$ be a prime power, and let $RS_k(\mathbb{F}_{q},\mathbb{F}_{q}^{*})$ denote the standard Reed–Solomon code of dimension $k$ evaluated at all nonzero elements of…

A Reed–Solomon code is obtained by evaluating low-degree polynomials over a finite field at a chosen set of field elements; a random Reed–Solomon code uses a randomly selected eval…

Let $\mathbb{F}_q$ be a finite field, let $D=\mathbb{F}_q^*$ be the evaluation set of a primitive Reed–Solomon code with code length $n=q-1$, dimension $k$, and codebook…

Let $\mathcal S=(S_1,\dots,S_n)$ be a generic zero pattern for $k\times n$ matrices: for every $I\subseteq [k]$, it satisfies … An $(n,k)$-code attains $\mathcal S$ if it has a gen…

Let ${\bf C}$ be a Reed–Solomon code of length $n$ and dimension $k$, and let $d_{insdel}$ denote its insertion-deletion distance. Reed–Solomon insdel-distance upper-bound conjectu…

Projective deep-hole conjecture. The set

Let a standard Reed–Solomon code have dimension $k$ over a finite field, and identify a received vector with the values of a polynomial on the evaluation set. A deep hole is a rece…

Let $f+zg$ be an affine line whose points are words, and let the Reed–Solomon code and the corresponding interleaved Reed–Solomon code be the codes under consideration. A point is…

Fixed-rate puncture conjecture. For an $[n,k,d]_q$ GRS code ${\mathcal C}$ of fixed rate $R$, the average number of punctures needed for $\operatorname{GRS\text{-}cover}$ to succee…

Puncture-count conjecture. For an $[n,k,d]_q$ GRS code, the average number of punctures needed for $\operatorname{GRS\text{-}cover}$ to succeed in returning a codeword within the c…

Let an interleaved Reed–Solomon code have rate $R$, interleaving order $s$, and suppose the errors are random. Multivariate interpolation decoding interpolates an $s+1$-variate pol…

Let $C$ be an $[n,k,d]_q$ generalized Reed–Solomon (GRS) code, and consider the covering algorithm that repeatedly punctures the received word and applies a GRS decoder. Let…

Let $C$ be a $q$-ary MDS code of length $q+1$ and dimension $k$, with $k>3$. A generalized doubly extended Reed–Solomon code is obtained from a doubly extended Reed–Solomon code by…

Let $n$ be the number of players, let $\alpha>0$ be a constant, and consider Shamir's secret sharing scheme with threshold $k=\alpha n$. A scheme is 1-bit local leakage resilient i…

Let $q$ be a prime power and let $\operatorname{PRS}(k)$ denote the projective Reed–Solomon code of dimension $k$ and length $q+1$. For $2\le k\le q-2$, let…

Reed–Solomon list-recoverability conjecture. The number of polynomials $P(X) \in \mathbb{F}_p[X]$ satisfying

Let $R$ be a fixed positive rate and let $\varepsilon>0$. Consider randomly punctured Reed–Solomon codes of block length $n$ that are $(1-R-\varepsilon,O(1/\varepsilon))$ list deco…

Shangguan's full-rank conjecture. The matrix $M_{G,(J_1,\ldots,J_t)}$ has full column rank.

Dau et al.'s GZP conjecture. Reed–Solomon codes over fields of size $q\geqslant n+k-1$ can have generator matrices with arbitrary patterns of zeros, provided that the pattern does…

For integers $L\geq 1$, $r\in[0,\frac{L}{L+1}]$, and $n$ such that $L\mid rn$, consider the largest size of an $(r,L)$ list-decodable code $C\subseteq[q]^n$ over an alphabet of siz…

Generalized Singleton bound conjecture. The generalized Singleton bound is tight for Reed–Solomon codes over sufficiently large fields.

Let $[n,k]$ denote a Reed–Solomon code with an $\epsilon$-MSR repair scheme, meaning that the repair bandwidth for every single failed node is at most $(1+\epsilon)$ times the cut-…

List decodability of Reed-Solomon codes up to capacity. For every $\rho>0$, there is a constant $C_\rho$ such that every Reed-Solomon code of length $n$ and rate $\rho$ is list-dec…

Lovett's linear independence conjecture. For integers $k,m,n\geq1$, if $\mathcal{V}\subseteq\mathbb{N}^n$ satisfies $V(k)$, then the polynomials in $P(k,\mathcal{V})$ are linearly…

Let $k\times n$ binary matrix $M=(m_{i,j})$ satisfy the MDS Condition: for every $r\in\{1,2,\cdots,k\}$, the union of the supports of any $r$ rows of $M$ has size at least $n-k+r$.…