List-Decoding Algorithms for Lifted Codes

DOI10.1109/TIT.2016.2538766MaRDI QIDQ2976857zbMATH OpenOpenAlexFDO

Authors Alan Guo, Swastik Kopparty

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0305

Mathematics Subject Classification ID

Decoding (94B35)

Abstract: 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 to 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 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).

Cited in

(21)

• Almost disjunctive list-decoding codes
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• List-decoding Barnes-Wall lattices
• scientific article; zbMATH DE number 7688196 (Why is no real title available?)
• List decoding of wavelet codes
• Erasures versus errors in local decoding and property testing
• scientific article; zbMATH DE number 7650399 (Why is no real title available?)
• Simplified High-Speed High-Distance List Decoding for Alternant Codes
• Algorithmic Results in List Decoding
• Erasures vs. errors in local decoding and property testing
• A Hensel lifting to replace factorization in list-decoding of algebraic-geometric and Reed-Solomon codes
• List Decoding for Binary Goppa Codes
• Solving ECDLP via list decoding
• On list decoding of certain \(\mathbb{F}_q\)-linear codes
• List Decoding of Direct Sum Codes
• List decoding of repeated codes
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• Local list recovery of high-rate tensor codes and applications
• Algorithmic Results in List Decoding
• Locality via partially lifted codes
• Lifted projective Reed-Solomon codes

This page was built for publication: List-Decoding Algorithms for Lifted Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976857)