Optimal List Decoding and Recovery of Random Code Ensembles

Definitions and mathematical statement

To make the terminology precise, use the following standard finite-alphabet framework; the source does not specify its parameter regimes. Let $n\geq 1$, let $\Sigma$ be a finite alphabet of size $q\geq 2$, and let a code be a nonempty subset $C\subseteq\Sigma^n$. Its rate is $R(C)=n^{-1}\log_q|C|$. For $x,y\in\Sigma^n$, define the Hamming distance by \[ d_H(x,y)=|\{i\in\{1,\ldots,n\}:x_i\ne y_i\}|. \] For a relative error radius $\rho\in[0,1]$ and an integer $L\geq 1$, the code is $(\rho,L)$-list-decodable if \[ \forall y\in\Sigma^n,\qquad |\{c\in C:d_H(c,y)\leq\rho n\}|\leq L. \] The integer-valued distance makes the radius condition equivalent to $d_H(c,y)\leq\lfloor\rho n\rfloor$.

For an integer $1\leq\ell\leq q$, the code is $(\rho,\ell,L)$-list-recoverable if, for every tuple of subsets $S_1,\ldots,S_n\subseteq\Sigma$ satisfying $|S_i|\leq\ell$, \[ \left|\left\{c\in C: |\{i\in\{1,\ldots,n\}:c_i\notin S_i\}|\leq\rho n \right\}\right|\leq L. \] Here $\ell$ bounds the input list size at each coordinate, while $L$ bounds the output list size. Taking singleton input lists recovers the list-decoding condition. These definitions concern combinatorial list sizes; the source supplies no required decoding or recovery algorithm or running-time bound.

A random code ensemble is a probability distribution $\mathcal D_n$ on nonempty codes in $\Sigma_n^n$. For specified parameter sequences $\rho_n$, $\ell_n$, and $L_n$, its list-decoding and list-recovery success probabilities are, respectively, \[ \Pr_{C\sim\mathcal D_n}\left[C\text{ is }(\rho_n,L_n)\text{-list-decodable}\right] \quad\text{and}\quad \Pr_{C\sim\mathcal D_n}\left[C\text{ is }(\rho_n,\ell_n,L_n)\text{-list-recoverable}\right]. \] An asymptotic requirement that either probability tend to $1$ as $n\to\infty$ is one possible interpretation, but it is not specified in the source.

Source question. Which random code ensembles have optimal list-decoding and list-recovery behavior, and what error radii and output list sizes do they achieve, as functions of the relevant rate, alphabet size, block length, and, for list recovery, input list size?

Unresolved qualifications. The supplied record does not specify the class of ensembles, parameter scaling, probability threshold, or benchmark defining "optimal." In particular, it does not identify a capacity boundary, an allowed gap from such a boundary, or an optimal dependence of $L$ on the other parameters. Thus this is a precise terminology framework for a research question, not a uniquely determined conjecture with fixed quantifiers. The original attributed wording asks about kinds of codes generally; the curated statement and talk title focus on random code ensembles.

Short English statement

Determine which random code ensembles achieve optimal tradeoffs among code rate, error radius, and output list size for list decoding and list recovery, with input list size also specified for recovery. The supplied source leaves the ensemble class, probability requirement, asymptotic regime, and meaning of optimality unresolved.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30006386$, title Optimal List Decoding and Recovery of Random Code Ensembles, source problem code catalogue entry, collection Oberwolfach Reports Open Problems; proposed year recorded as 2025. The record supplies no separate proposer.
• Supplied report citation: New Mathematical Directions in Coding Theory (2026), Oberwolfach Reports, DOI 10.4171/owr/2025/41, pp. 2187--2242. https://doi.org/10.4171/owr/2025/41. The supplied citation uses 2026, whereas the DOI and report label use 2025; this discrepancy is unresolved.
• Supplied attribution: Ray Li, List-Decoding and List-Recovery of Random Codes Ensembles, joint work with Omar Alrabiah, Venkatesan Guruswami, and Nikhil Shagrithaya.
• Supplied literature source: Oberwolfach Report 41 2025. https://ems.press/content/serial-article-files/52245.
• Supplied literature source: Near-Optimal List-Recovery of Linear Code Families. https://arxiv.org/abs/2502.13877.
• Supplied literature source: Random Reed--Solomon and Random Linear Codes. https://arxiv.org/abs/2406.02238.
• Supplied dated literature curation, checked 2026-08-22: the record labels the question open and reports capacity or near-optimal results for random linear codes and punctured Reed--Solomon codes in important regimes, while reporting no general characterization of optimally list-decodable and list-recoverable codes. This is the supplied dated assessment, not an independently verified literature conclusion; the relevant regimes and precise theorem statements are not supplied.
• The registry labels its statement corrected_verified and reports that the official report was checked, the question isolated, and its notation repaired. These are supplied provenance claims, not verification performed for this draft.