List-Decoding Algorithms for Lifted Codes
Alan Guo, Swastik Kopparty · IEEE Transactions on Information Theory · 2016
Lifted Reed-Solomon codes are a natural affine-invariant family of error-correcting codes, which generalize Reed-Muller codes. They were known to have efficient local-testing and local-decoding algorithms (comparable with the known algorithms for Reed-Muller codes), but with significantly better rate. We give efficient algorithms for list decoding and local list decoding of lifted codes. Our algorithms are based on a new technical lemma, which says that the codewords of lifted codes are low degree polynomials when viewed as univariate polynomials over a big field (even though they may be very high degree when viewed as multivariate polynomials over a small field).