Plenary Talk - Jet List Decoding

Daniel J. Bernstein

Fifty years ago Peterson introduced a polynomial-time algorithm to decode floor(t/2) errors in a degree-t Reed–Solomon code. The algorithm is given a received word as input; the distance of the code is t+1, guaranteeing that there is at most one codeword whose Hamming distance from the input is at most floor(t/2); the algorithm output is that codeword, if it exists.

Unfortunately, polynomial time does not mean fast. Fortunately, in the 1960s Berlekamp introduced an algorithm running in essentially quadratic time, and in the 1970s Justesen and Sarwate introduced an algorithm running in essentially linear time, scaling astonishingly well to codes of very large length. More detailed analyses and optimizations, improving the performance of these algorithms and other decoding algorithms with the same floor(t/2) effectiveness, have been a continuing topic of research since then.

What if there are more than floor(t/2) errors? In 1998 Guruswami and Sudan introduced a polynomial-time algorithm to decode w errors in a length-n degree-t Reed–Solomon code for any w below the big-field Johnson bound n-sqrt(n(n-t-1)). This bound is larger than t/2 by approximately t^2/8n. The algorithm is called a list-decoding algorithm because it sometimes outputs a list of more than one possible codeword; the increased effectiveness of the algorithm means that there is no longer a guarantee of uniqueness.

Unfortunately, as before, polynomial time does not mean fast. Fortunately, optimizations have reduced the algorithm cost to essentially linear in the code length and sub-quartic in an algorithm parameter L that bounds the size of the output list. Reducing L makes the algorithm much faster but also forces a larger gap between w and n-sqrt(n(n-t-1)): specifically, for the Guruswami–Sudan algorithm the minimum possible value of the product L(n-sqrt(n(n-t-1))-w) is approximately t. For many years this seemed optimal, but in 2007 Wu introduced a new list-decoding algorithm with a better tradeoff between L and w, reducing L by a factor of approximately 8n/t and accelerating the algorithm by a power of the same factor.

What if there are more than n-sqrt(n(n-t-1)) errors? In 2000 Koetter and Vardy showed how to take advantage of errors in a subfield: they introduced a polynomial-time algorithm that decodes approximately t^2/8n(q-1) errors more than the Guruswami–Sudan algorithm for the F_q subfield subcode of any length-n degree-t generalized Reed–Solomon code. For example, the Koetter–Vardy algorithm doubles the benefit of list decoding for BCH codes, and more generally for classical binary Goppa codes.

Wu adapted his list-decoding algorithm to BCH codes, but it is not clear that the same approach generalizes further, or that it can be combined with other speedups. I will present a new list-decoding algorithm, jet list decoding, that decodes beyond Guruswami–Sudan for much more general classical Goppa codes, while allowing state-of-the-art speedups and providing a Wu-type reduction in list size. The same idea should also work for higher-genus AG codes.

The audience is not expected to have prior exposure to list-decoding algorithms. All necessary background will be introduced in the talk.