38 problems

Let $d$ be fixed, and consider the degree-$d$ Reed–Solomon code with evaluation set $FbbF_q$. A random puncturing is obtained by retaining a random subset of evaluation coordinates…

Let $A(n,1)$ denote the maximum size of a binary single-deletion-correcting code of length $n$, and let $VT_0(n)$ be the binary Varshamov–Tenengolts code with syndrome $0$. A code…

Let a random parity-check code have length $n$, $m=n(1-R)$ parity checks, and arbitrary degree distributions. The adaptive LP decoding algorithm is the iterative algorithm that add…

Adaptive LP decoding conjecture. As $n$ increases, the algorithm converges with probability arbitrarily close to $1$ in at most $b1$ iterations and with at most $b2$ final parity-c…

Let $X_1,\ldots,X_k$ and $Y$ be sets, let $f\colon X_1\times\cdots\times X_k\to Y$ be a function, and let ${\cal G}\left<f,q,l\right>$ denote the generalized Ulam game in which Pau…

Low-dimensional sum-set decomposition conjecture. For every choice of $\ell\in\mathbb N$, $\varepsilon>0$, and $R>0$, the decomposition above exists for all sufficiently large fold…

Maturana–Rashmi's conjecture. Under the Uniform Cost Assumption, every stable linear MDS $(n^{I},k^{I}={\lambda}^{F}k^{F};n^{F},k^{F})$ convertible code with $r^{F}<r^{I}$ and…

Chen–Zhang's conjecture. For the stated parameters, folded Reed–Solomon codes achieve list-recovery radius arbitrarily close to $\rho^*$ with input list size $ell$ and output list s…

Multiple burst-substitution redundancy conjecture.

Low-power error-correcting cooling code density conjecture. Under this condition,

Nonexistence conjecture. Let $q \ge 6$ be a non-prime power. Then, there are no perfect error correcting codes over $Z_q$.

Let $H(n,q,s,a)$ denote a Helberg code with length $n$, alphabet size $q$, deletion parameter $s$, and residue $a$. Let $a$ be the residue corresponding to the maximum number of co…

Let $VT_{(a,b)}(n;4)$ be a quaternary Varshamov–Tenengolts code, let $\phi$ be a Naisargik map, and let $D_1(X)$ denote the set of binary sequences obtained from $X$ by one deletio…

For each integer $k e 0$, let a Kerdock spherical code be the spherical code in $\mathbb{R}^{2^{2k}}$ constructed from the Kerdock binary code, with $2^{4k}+2^{2k+1}$ points and…

Let $G$ be a $(c,d,\alpha,\delta)$-bipartite expander and let $C_0\subseteq\mathbb{F}_2^d$ be an inner code with minimum Hamming distance $d(C_0)\ge d_0$. Let…

Let $q=p^s$, where $p$ is an odd prime and $s\ge 2$, and set $h=\frac{p-1}{2}$. Let $\mathcal{C}_{(q,q+1,3,h)}$ denote the BCH code in question. BCH-code conjecture. The code…

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…

Let $q$ be a power of a prime, $(q-1)/2le n-k$, and $k<n\le q$. Let ${\bf a}=(\alpha_1,\ldots,\alpha_n)$ and let ${\bf w}$ denote the multiplier vector from the associated MDS code…

Heng et al.'s conjecture. For each $3\leq k\leq q-2$, the linear code $\mathcal{C}_k$ is a $1$-MDS $[q-1,k,q-k-1]_q$ code, and the minimum-weight codewords of both $\mathcal{C}_k$…

Heng's conjecture. If $q>2$, then $\widetilde{\overline{C_D}}$ is a $[q+1,3,q-2]_q$ NMDS code. This conjecture concerns the remaining family of NMDS codes identified by Heng; provi…

Let $k$ be an even positive integer and let $n>k$ be an integer. Write $d_2^{E}(n,k)$ for the relevant extremal minimum distance of binary LCD codes, and call a binary LCD code eve…

Fix an integer $q\ge 2$. A $q$-ary code of length $n$ and distance $d$ is a subset of $[q]^n$ whose elements are pairwise separated by Hamming distance at least $d$, and let…

Let $G=([n],E)$ be a $k$-uniform hypergraph, and let $q(G)$ be the smallest alphabet size for which there are encoding and decoding functions recovering every message from the symb…

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-…

Let $q$ be the alphabet size, and let an optimal locally recoverable code have minimum distance $d$ and locality $r$. Length conjecture for optimal locally recoverable codes. Every…