Abstract. Reed–Solomon error-correcting codes are ubiquitous across computer science and information theory, with applications in cryptography, computational complexity, communication and storage systems, and more. Most works on efficient error correction for these codes, like the celebrated Berlekamp–Welch unique decoder and the (Guruswami–)Sudan list decoders, are focused on measuring error in the Hamming metric, which simply counts the number of corrupted codeword symbols. However, for some applications, other metrics that depend on the specific values of the errors may be more appropriate. This work gives a polynomial-time algorithm that list decodes (generalized) Reed–Solomon codes over prime fields in ℓp (semi)metrics, for any 0 < p ≤ 2. Compared to prior algorithms for the Lee (ℓ1) and Euclidean (ℓ2) metrics, ours decodes to arbitrarily large distances (for correspondingly small rates), and has better distance-rate tradeoffs for all decoding distances above some moderate thresholds. We also prove lower bounds on the ℓ1 and ℓ2 minimum distances of a certain natural subclass of GRS codes, which establishes that our list decoder is actually a unique decoder for many parameters of interest. Finally, we analyze our algorithm’s performance under random Laplacian and Gaussian errors, and show that it supports even larger rates than for a corresponding amount of worst-case error in ℓ1 and ℓ2.

Based on joint work with Chris Peikert.