Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets

A code is a set of codewords over some alphabet. Assume the codewords have length $n$ and the alphabet has size $q$. An important parameter of the code is the rate $R$, which is the logarithm base $q$ of the number of codewords, divided by $n$. This measures the proportion of the length of a codeword that encodes useful (i.e. non-redundant) information. When receiving an encoded message, a number of letters might have been corrupted and the goal is then to recover the original message (one of the codewords) that has been sent. This is typically possible if every word on $n$ letters on the alphabet is at distance at most $pn$ (in Hamming distance) from at most one codeword, where $p\in [0,1]$ is called the error parameter. The Singleton bound states that the error parameter cannot exceed $(1-R)/2$ and a number of codes are known to achieve this bound.

In a natural extension, called list-decoding, each word is allowed to be at distance at most $pn$ from at most $L$ codewords, for some fixed integer $L$. In this context, the analogue of the Singleton bound is that the error parameter cannot exceed $(1-R)L/(L+1)$. For large (but constant) $L$, it might thus be possible to get very close to $1-R$ (a barrier called the list-decoding capacity), and thus almost double the error compared with the case $L=1$. When this is indeed the case, the code is said to achieve list-decoding capacity.

The present paper shows that two natural types of random codes achieve list-decoding capacity. The first one is a randomized version of Reed-Solomon codes. Starting with a random $n$-tuple $x_1,\ldots,x_n$ of distinct elements of the Galois field $GF(q)$ (assuming $q$ prime, and greater than $n$ plus a sufficiently large constant), the codewords consist of all the words of the form $f(x_1),\ldots,f(x_n)$ where $f$ is a polynomial of degree less than $Rn$ over $GF(q)$. It was known that such codes achieve list-decoding capacity, but only when the alphabet size $q$ was exponential in $n$.

The second type of random codes studied are random linear codes, which are random linear subspaces of dimension $Rn$ of the vector space $GF(q)^n$. In this case there is no restriction of the type $q\ge n+C$ and $q$ is only assumed to be a sufficiently large constant.

Part of the proof of both results relies on connecting list-decoding of codes to weak-partition-connectivity of hypergraphs and then using the properties of some specific orientations of these hypergraphs.