34 problems

For a positive integer $n$, write $[n]=\{1,\ldots,n\}$. For subsets $I_1,\ldots,I_t\subseteq[n]$, define their weight by … and write…

Guruswami–Sudan conjecture for binary BCH codes. The Guruswami–Sudan algorithm should be modifiable so as to achieve the Johnson bound for binary BCH codes.

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

For a discrete memoryless arbitrarily varying channel with state constraint $\Lambda$, let the converse region be the rate region established by Theorem. Converse-region conjecture…

Let the lower bounds in Proposition … should constitute a family of multivariate fidelities that can be used to prove list-decoding error exponents. A quantum generalisation of lis…

Let $\mathcal{M}$ be a classical-quantum channel, and let $E_L^{\emptyset}(0^+,\mathcal{M})$ denote its unassisted zero-rate list-decoding error exponent with list size $L$. Let…

Conjecture. These bounds can be improved, without changing the code structure, to rate $\Omega(\varepsilon)$ and list size $O(1/\varepsilon)$ by improving the analysis method.

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.

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…

Let $f$ be a Boolean function, and let $x,y$ be independent uniformly random Boolean inputs. A function is correlated with a character if there is some $S$ such that it agrees with…

List-decoding Plotkin-point conjecture. In this case, the largest code size is

Let $C\geq1$ be real, let $t\geq3$ be a positive integer, and let $k$ be a positive integer. For subsets $I_1,\ldots,I_t\subseteq[n]$, write $\operatorname{wt}(I_j:j\in J)$ for the…

Let $L$ be a positive integer, let $C\geq1$ be a positive real, and let $R=\frac{k}{n}$ be the rate of an $[n,k]$ Reed–Solomon code. A code is list-decodable from radius $\rho$ wit…

Let $n$ be a positive integer, let $1\le k<n$, let $R=\frac{k}{n}$, and let $\varepsilon>0$ satisfy $\varepsilon n\in\mathbb{Z}$. A Reed–Solomon code is list-decodable from radius…

For a code of rate $R$ over a finite field, list-decodable from relative radius $r$ with list size $L$ means that every Hamming ball of radius $r n$ contains at most $L$ codewords.…

A Reed–Solomon code is obtained by evaluating polynomials of degree less than $k$ at $n$ distinct elements of a finite field. For a prime power $q$, let an $[n,k]$-RS code be defin…

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…

Let $\Lambda$ be a random lattice drawn from the Haar distribution, let $\mathcal B$ be a measurable subset of the ambient space with nonempty interior, and let $Y$ denote the Pois…

Let $\delta>0$ denote the gap between the list-decoding capacity and the transmission rate. A lattice code is required to operate at rate $\frac12\log(P/N)-\delta$, and its list si…

Let $q$ be a prime power, let $0<p<1-1/q$, and let $H_q(p)$ denote the $q$-ary entropy. A random linear code of rate $1-H_q(p)-\delta$ is chosen uniformly among linear codes of tha…

Let $\delta\coloneqq\frac{1}{2}\log\frac{P}{N}-R$ measure the gap between the transmission rate $R$ and the list decoding capacity of the quadratically constrained adversarial chan…

Consider a minimal convolutional code with $m$ memory elements and a degree-$v$ distance-spectrum-optimal CRC code, used together under serial list Viterbi decoding at a fixed SNR.…

Let $m$ be the degree of the CRC code, and let $\operatorname{P}^{1}_{\operatorname{UE}}$ and $\operatorname{P}^{1}_{\operatorname{F}}$ denote, respectively, the undetected-error p…

Let $k$ be the message length, let $cell$ and $c$ be Guess & Check (GC) code parameters with $cell=Omega(\log k)$ and $c\geq 2\delta$, and let $L_{max}$ denote the maximum list siz…