Correcting errors beyond the Guruswami-Sudan radius in polynomial time

We introduce a new family of error-correcting codes that have a polynomial-time encoder and a polynomial-time list-decoder, correcting a fraction of adversarial errors up to τ_M = 1 - ^M+1√(M^MR^M) where R is the rate of the code and M ≥ 1 is an arbitrary integer parameter. This makes it possible to decode beyond the Guruswami-Sudan radius of 1 √R for all rates less than 1/16. Stated another way, for any ε > 0, we can list-decode in polynomial time a fraction of errors up to 1 - ε with a code of length n and rate Ω(ε/log(1/ε)), defined over an alphabet of size n^M = n^O(log(1ε))/. Notably, this error-correction is achieved in the worst-case against adversarial errors: a probabilistic model for the error distribution is neither needed nor assumed. The best results so far for polynomial-time list-decoding of adversarial errors required a rate of O(ε²) to achieve the correction radius of 1 - ε. Our codes and list-decoders are based on two key ideas. The first is the transition from bivariate polynomial interpolation, pioneered by Sudan and Guruswami-Sudan [1999], to multivariate interpolation decoding. The second idea is to part ways with Reed-Solomon codes, for which numerous prior attempts at breaking the O(ε²) rate barrier in the worst-case were unsuccessful. Rather than devising a better list-decoder for Reed-Solomon codes, we devise better codes. Standard Reed-Solomon encoders view a message as a polynomial f(X) over a field F_q, and produce the corresponding codeword by evaluating f(X) at n distinct elements of F_q. Herein, given f(X), we first compute one or more related polynomials g₁(X), g₂(X), ..., g_M-1(X) and produce the corresponding codeword by evaluating all these polynomials. Correlation between f(X) and g_i(X), carefully designed into our encoder, then provides the additional information we need to recover the encoded message from the output of the multivariate interpolation process.