We show that Reed-Solomon codes of dimension $k$ and block length $n$ over any finite field $\mathbb{ F}$ can be deterministically list decoded from agreement $\sqrt{ (k-1)n}$ in time $\text{ poly}(n, \log |\mathbb{ 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 $\text{ poly}(n, \log |\mathbb{ F}|)$ or were deterministic with time complexity depending polynomially on the characteristic of the underlying field. In particular, over a prime field $\mathbb{ F}$, no deterministic algorithms running in time $\text{ poly}(n, \log |\mathbb{ 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 $\text{ poly}(\log |\mathbb{ F}|)$ dependence on the field size in its time complexity for every finite field $\mathbb{ 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.
Categories: cs.CC cs.IT math.IT