List-decoding multiplicity codes

DOI10.4086/TOC.2015.V011A005MaRDI QIDQ2941640zbMATH OpenOpenAlexFDO

Authors Swastik Kopparty

Publication date 21 August 2015

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

differential equationserror-correcting codesList-decodingpolynomials

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Symbolic computation and algebraic computation (68W30) Decoding (94B35)

Abstract: Multiplicity codes are algebraic error-correcting codes generalizing classical polynomial evaluation codes, and are based on evaluating polynomials and their derivatives. This small augmentation confers upon them better local decoding, list-decoding and local list-decoding algorithms than their classical counterparts. We survey what is known about these codes, present some variations and improvements, and finally list some interesting open problems.

Recommendations

• Some remarks on multiplicity codes
• High-rate codes with sublinear-time decoding
• High-rate codes with sublinear-time decoding
• Explicit capacity-achieving list-decodable codes
• Decoding Reed-Muller codes over product sets

Cites work

• List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes
• List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
• Subspace evasive sets

Cited in

(37)

• List cascade decoding
• On list decoding of certain \(\mathbb{F}_q\)-linear codes
• Explicit subspace designs
• List-decoding Barnes-Wall lattices
• Fast systematic encoding of multiplicity codes
• Almost disjunctive list-decoding codes
• List Decoding of Crisscross Errors
• Some remarks on multiplicity codes
• scientific article; zbMATH DE number 5380293 (Why is no real title available?)
• Better Binary List-Decodable Codes Via Multilevel Concatenation
• List decoding of repeated codes
• Decoding Reed-Muller codes over product sets
• Group homomorphisms as error correcting codes
• Synchronization strings: list decoding for insertions and deletions
• Low-density parity-check codes achieve list-decoding capacity
• Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
• Derandomization from Algebraic Hardness
• Erasures vs. errors in local decoding and property testing
• Local list recovery of high-rate tensor codes and applications
• List decoding of wavelet codes
• List Decoding of Direct Sum Codes
• Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives
• High-rate codes with sublinear-time decoding
• High-rate codes with sublinear-time decoding
• List-Decoding with Double Samplers
• Lifted Multiplicity Codes and the Disjoint Repair Group Property
• scientific article; zbMATH DE number 7650399 (Why is no real title available?)
• Erasures versus errors in local decoding and property testing
• Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
• Generalized Singleton Bound and List-Decoding Reed–Solomon Codes Beyond the Johnson Radius
• Hermite interpolation with error correction. Fields of zero or large characteristic and large error rate
• Algorithmizing the multiplicity Schwartz-Zippel lemma
• A criterion for decoding on the binary symmetric channel
• Duals of multiplicity codes
• List-decodable Byzantine robust PIR: lower communication complexity, higher Byzantine tolerance, smaller list size
• Near-optimal list-recovery of linear code families

This page was built for publication: List-decoding multiplicity codes

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