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

Let $m$ be a positive integer, let $h$ be as in Theorem 8, and let $\mathcal{C}_{(2,2^m+1,3,h)}$ denote the BCH code in that theorem. Its minimum distance is denoted by $d$. Minimu…

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…

Goppa's conjecture. The Gilbert–Varshamov bound is tight in the binary case; equivalently, the asymptotic achievable rate equals the Gilbert–Varshamov bound.

Let $p_e$ be the point where the 1RSB and replica-symmetric (RS) error exponents coincide, with $p_e>p_{\rm 1RSB}$. Let $p_{\rm RS}$ denote the spinodal point below which the RS so…

Let $F$ be a finite alphabet of cardinality $q\geq 2$, let $n$ be a positive integer, and let $V=F^n$. For words $\mathbf{x},\mathbf{y}\in V$, define the Hamming distance…

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…

Let $q$ be the parameter of the Grassl–Rötteler code, let $k$ be its dimension, and let $d$ denote the minimum distance of its puncture code. Grassl–Rötteler conjecture. The minimu…

A classical $[n,k]_q$ MDS code is nontrivial when it is not one of the cases excluded by the stated bound. MDS conjecture. If there is a nontrivial $[n,k]_q$ MDS code, then…

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…

Universal list-size conjecture. The list size is at most $n$ for list decoding up to the Johnson bound for any code.

Belief propagation (BP) is understood through its fixed points, and PCS-style analysis concerns the study of instanton spectra using an accelerated method. BP analysis conjecture.…

Convergence conjecture. For $\kappa\to+\infty$, this randomized cyclic coordinate-ascent algorithm cannot get stuck at a suboptimal point and therefore converges to a maximum of th…

Let a linear-programming decoding scheme have pseudo-codewords with components $\sigma_i^{(k_*)}$, and define the estimated effective distance by … where the minimum is taken over…

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…

Conjecture on the structure underlying their performance. The observed performance results are a consequence of the column-weight-four array codes having minimum distance significa…

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…

Let $m$ be a positive integer. For each integer $\delta$ with $2\leq \delta\leq 2^m-1$, let $\mathcal{C}_{(2,m,\delta)}$ be the binary primitive narrow-sense BCH code of length…

Let $F$ be a finite alphabet of cardinality $q \geq 2$, let $n$ be a positive integer, and let $V=F^n$. For words $\mathbf{x},\mathbf{y}\in V$, define their Hamming distance…

Let $P=\{a,b\}$ be a prefix-free binary block set, with block lengths $\ell_a=|a|\leqslant\ell_b=|b|$, and suppose that $K^{\star}(a,b)<\infty$. Two-block depth law. If…

For each integer $k\geqslant3$, define binary blocks … with lengths $\ell_a=|a_k|=2k$ and $\ell_b=|b_k|=2k+2$, and let $P_k=\{a_k,b_k\}$. The quantity $L_{P_k}$ denotes the relevan…

Let $\mathbf{H}$ be the parity-check matrix of a BCH code, and compare its row density with that of parity-check matrices used for LDPC codes. Density conjecture. The root cause of…

Alderson's dimension bound conjecture. The maximum dimension $k$ of a length-maximal $A^s$ MDS code is at most $5$.

Let $\mathbb{F}_q$ be a finite field, and let $\mathcal{C}\subseteq\mathbb{F}_q^n$ be a non-trivial MDS code of dimension $k$. MDS conjecture. If such a code exists, then … except…