Deterministic List Decoding of Reed-Solomon Codes

We show that Reed-Solomon codes of dimension k and block length n over any finite field F can be deterministically list decoded from agreement (k -1)n in time poly(n, log |F|).

Prior to this work, the list decoding algorithms for Reed-Solomon codes, from the celebrated results of Sudan and Guruswami-Sudan, were either randomized with time complexity poly(n, log |F|) or were deterministic with time complexity depending polynomially on the characteristic of the underlying field. In particular, over a prime field F, no deterministic algorithms running in time poly(n, log |F|) were known for this problem.

Our main technical ingredient is a deterministic algorithm for solving the bivariate polynomial factorization instances that appear in the algorithm of Sudan and Guruswami-Sudan with only a poly(log |F|) dependence on the field size in its time complexity for every finite field F. While the question of obtaining efficient deterministic algorithms for polynomial factorization over finite fields is a fundamental open problem even for univariate polynomials of degree 2, we show that additional information from the received word can be used to obtain such an algorithm for instances that appear in the course of list decoding Reed-Solomon codes.